Answer to Question #254901 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^2*log(n)$ , $g(n) = n^3$

Now to show $f(n)=O(g(n))$ when number of operation increases i.e., $n\rightarrow \infty$ then

$\frac{f(n)}{g(n)}=\frac{4n^3+5n^2.log\ n}{n^3}=4+\frac{5.log\ n}{n}$

Now, $\lim_{n\to\infty}$ $\frac{f(n)}{g(n)}=4+\lim_{n\to\infty}\frac{5.log\ n}{n}$

$=4+5\lim_{n\to\infty} \frac{1/n}{1}$ [Using L'Hospital Rule]

$=4+5\times0=4$

So, $|\frac{f(n)}{g(n)}|\rightarrow 4$ as $n\rightarrow\infty$

So, $f(n)=O(g(n))$