Why is this big oh $O(n^3)$

Question

Why is this big oh $O(n^3)$?

(b) Give a good big-Oh bound on the function $$f(n)=2^{\log_2 n} n^2 + 3n^2 \log_2 n +n -17$$

I am not sure on how to solve this. If someone could help me solve, I will be thankful as I have an exam tomorrow.

Answer 1

The answer is $O(n^3)$. Why?

The first term reduces to $n^3$. We can see the equality by considering the definition of logarithm:

$\log _2 n$ = the number such that 2 raised to this power equals n

Thus $2^{\log_2 n} =n$ and furthermore $2^{\log_2 n} n^2 = n\cdot n^2 = n^3$.

The second term is $\Theta(n^2 \log_2 n) = o(n^3)$ hence irrelevant.

Finally the third and fourth order terms are also clearly $o(n^3)$.

Hence $O(n^3)$ is the tightest big Oh bound possible (incidentally the function is actually even $\Theta(n^3)$).