6,494 views
1 votes
1 votes

f(n) = n2 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 * ( log216)10  = 16 * ( 4 )10

and f(n) = 256 * log216 = 256*4

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

3 Answers

Best answer
10 votes
10 votes

$$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)$

edited by
0 votes
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 .....
0 votes
0 votes
F(n)=n^2.logn

G(n)=n(logn)^10

n.(logn)^10<=C.n^2.logn

Here we can cancel out n and logn

Remaining things i.e

Logn^9<=C.n

Taking log both side

9.loglogn <=C.logn

Pls anybody inform if i'm wrong

Related questions

0 votes
0 votes
3 answers
1
radha gogia asked Jan 29, 2016
2,029 views
If c is non-negative but not infinite then :1.f(n)=O(g(n))2.f(n)=&#8854;(g(n)) According to me :it is saying that c is non-negative and not infinite so if g(n) tends to z...
3 votes
3 votes
1 answer
3
gate-17 asked Aug 7, 2016
2,808 views
consider the following functions f(n)=log*(log n) , g(n)=log(log* n) relations between these 2 function. please help
7 votes
7 votes
2 answers
4
anshul namdeo asked Jun 6, 2016
12,700 views
Which of the following is true? a. h(n) is O(f(n)) b. h(n) is O(g(n)) c. g(n) is not O(f(n)) d. f(n) is O(g(n))Why not answer c because both f(n) and g(n) have of same or...