Question

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

Answer 1

The proof is in the explanation

Step-by-step 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)} + (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))`