Answer to Question #270359 in Discrete Mathematics for Nancy

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(n)=4n^2+5n^2log(n)\le4n^3+5n^3=9n^3=9g(n)$

so f(n) is O(g(n))