Question

Prove that f(n) = 20n3 + 10nlogn + 5 is O(n3)

Answer 1

Answer:

The proof is in the explanation

Explanation:

$f(n)$ is $O(n^{3})$ if $f(n) \leq cn^{3}$ for $n \geq n_{0}$.

So, basically, we have to solve the following inequality

$f(n) \leq cn^{3}$

$20n^{3} + 10n\log{n} + 5 \leq cn^{3}$

Dividing everything by $n^{3}$ to simplify, we have

$20 + \frac{10\log{n}}{n^{2}} + \frac{5}{n^{3}} \leq cn^{3}$

I am going to use $n = n_{0} = 1$. So

$20 + 5 \leq c$

$c \geq 25$

There is a solution for the inequality, which proves that $f(n) = 20n^{3} + 10n\log{n} + 5$ is $O(n^{3})$