Question

A particular algorithm increases in time as the number of operations, n, increases.

Suppose the time complexity of this algorithm is given by: f(n) =4n³+5n² * log(n).

Show that f(n) is O(g(n)) for g(n) = n³.

Answer 1

$f(x)=O(g(x))$ if there exists a positive real number M and a real number x₀ such that

$|f(x)|\le Cg(x)$ for all $x\ge x_0$

So, we have:

f(n) =4n³+5n² * log(n) < $5g(x)=5n^3$ for $x\ge 2$

where $C=5,x_0=2$