You should never evaluate relative growth of functions by plugging in values.

The Gateway to Computer Science Excellence

+1 vote

f(n) = n^{2} logn

g(n) = n (logn)^{10}

Ans given as g(n) = O(f(n)) and f(n) != O(g(n))

But , if I take base of log as 2

then for random value of n ( say 16)

g(n) = 16 * ( log_{2}16)^{10 }= 16 * ( 4 )^{10}

and f(n) = 256 * log_{2}16 = 256*4

So , will it not be f(n) = O(g(n)) ?

+8 votes

Best answer

$$f(n) = n^2 \log n, \qquad g(n) = n \log^{10} n$$

Dividing both these functions by $(n \log n)$, we get:

$$F(n) = n, \qquad G(n) = \log^9 n$$

Since * any polynomial function grows faster than any logarithmic function*, we have:

$F(n)$ grows faster than $G(n)$

$\implies$ $f(n)$ grows faster than $g(n)$

$\implies n \log^{10} n = O(n^2 \log n)$

0 votes

These function have not uniformity in comparison actually .... ans is C

If F(n) = O(g(n)) then F(n) <= C g(n) which after simplfying gives

n < c (logn)^9 , now put n = 2^10 , 2^20 this will be true but put 2^60 , 2^80 it will fail the identity for same constant which we derived in for 2^10 or 2^20 .....

If F(n) = O(g(n)) then F(n) <= C g(n) which after simplfying gives

n < c (logn)^9 , now put n = 2^10 , 2^20 this will be true but put 2^60 , 2^80 it will fail the identity for same constant which we derived in for 2^10 or 2^20 .....

52,217 questions

59,907 answers

201,099 comments

118,145 users