Question

Consider the function f(n) = 35n³+ 2n³log(n) − 2n²log(n²) which represents the complexity of some algorithm.

(a) Find a tight big-O bound of the form g(n) = n^p for the given function f with some natural number p. What are the constants C and k from the big-O definition?

(b) Find a tight big-Ω bound of the form g(n) = n^p for the given function f with some natural number p. What are the constants C and k from the big- Ω definition?

(c) Can we conclude that f is big−Θ (n^p) for some natural number p?

Answer 1

a)

$f(n)=O(g(n))$ if

$Cg(n)\ge f(n)$

$C>0,\ n\ge n_0$

So:

for $n_0=1$

$36n^3\ge 35n^3+ 2n^3log(n) − 2n^2log(n^2)$

$C=36,\ p=3,\ k=1$

b)

$f(n)=O(g(n))$ if

$Cg(n)\le f(n)$

for $n_0=1$

$35n^3\le 35n^3+ 2n^3log(n) − 2n^2log(n^2)$

$C=35,\ p=3,\ k=1$

c)

$f(n)=\theta(g(n))$ if

$C_2g(n)\le f(n)\le C_1g(n)$

for $n_0=1$

$35n^3\le 35n^3+ 2n^3log(n) − 2n^2log(n^2)\le 36n^3$

So, we can conclude that $f(n)=\theta(g(n))$ for $p=3$