Why is $f(n) = Θ(g(n))$ where, $f(n) = n^4 - n^3$ and $g(n) = 16^{\log(n)}$

51 Views Asked by At

I saw an example that claims that: $f(n) = Θ(g(n))$ where, $f(n) = n^4 - n^3$ and $g(n) = 16^{\log(n)}$

I can understand how the polynomial f(n) is translated into $O(n^4)$ and that it also has a lower bound of $Ω(n^3)$

How can we prove that g(n) lies between them?

1

There are 1 best solutions below

0
On BEST ANSWER

$f(n)$ is $O(n^4)$ and $\Omega(n^4)$, i.e. $f(n) = \Theta(n^4)$.

Assuming that the logarithm is base $2$, $g(n) = 16^{\log(n)} = (2^4)^{\log(n)} = (2^{\log(n)})^4 = n^4$.