The Gateway to Computer Science Excellence
+1 vote
1.3k views

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

in Algorithms by Active (3.8k points) | 1.3k views
+2
You should never evaluate relative growth of functions by plugging in values.
+1
Thanks sir :)
0
And if you do decide to take risky short cut and plug in values makes sure you plus in large ones like 2^1024 etc. and double check with more values.

3 Answers

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

by Veteran (60.4k points)
edited by
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 .....
by (121 points)
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
by (15 points)
0
True explanation
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,154 answers
193,759 comments
93,725 users