search
Log In
49 votes
6.8k views

Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct?

  1. $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$
  2. $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$
  3. $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$
  4. $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$
in Algorithms
edited by
6.8k views
1
Here for getting quick answer first do minimization on both the sides then apply log on both the sides.

For cross verification of your answer follow whatever Arun ji has mentioned in his answer.
9
taking log in all case  is not a good practice .

it sometimes give right answer & sometime give wrong answer

if we take log of n^2  && n^100

both are same according to log

log is not always a deciding factor

i hope it help u
1

@yankur9

First do minimization on both the sides

2

Given,

f(n) = n2 log n and  g(n) = n(log n)10

which means 

f(n) = n*n log n and g(n) = n(log n)10

here n is common on both sides so cancel them

then we get,

n log n for f(n) and (log n)10   for g(n)

which means f(n) is larger.

 

 

 

 

0

n(logn)^10

=> n*10*logn

=> 10*n*logn

=>n*logn(10 is constant)

Now, n2logn > nlogn

2

@vishalshrm539

if it is  $\log n^{10}$ then you can do 10 logn but it is not so

4

0
good and simple one thanks

8 Answers

32 votes
 
Best answer

A more formal approach:

$f(n) = n^2 \log n$

$g(n) = n (\log n)^{10}$

We can use the limit definition of $O$-notation

http://cse.unl.edu/~choueiry/S06-235/files/Asymptotics-HandoutNoNotes.pdf

$\displaystyle{\lim_{n \to \infty }} \frac{f(n)}{g(n)} = 0, \implies  f(n) = o(g(n))$
small $o$ implying $f$ is strictly asymptotically lower than $g$. Also by definition, $o \implies O \text{ but } O \not\implies o$.

$\displaystyle{\lim_{n\to \infty}} \frac{f(n)}{g(n)} = c,  c > 0 \implies f(n) = \Theta(g(n))$

$\displaystyle{\lim_{n \to \infty}} \frac{f(n)}{g(n)} = \infty, \implies  f(n) = \omega(g(n))$
small $\omega$ implying $f$ is strictly asymptotically higher than $g$. Also by definition, $\omega \implies \Omega, \text{ but } \Omega \not \implies \omega.$

We can use this to prove the above question

For any $k > 0$

 $\displaystyle{\lim_{n \to \infty}} \frac{(\log n)^{k}}{ n}$

Applying L'Hôpital's rule,

$\implies \displaystyle{ \lim_{n \to \infty}} \frac{ k*(\log n)^{k-1}}{ n}$

$= \displaystyle{\lim_{n \to \infty}}  \frac{ k!}{n} = 0$

So, $(\log n)^k = o(n)$

Now for large $n$, $n >> (\log n)^9$

i.e., $n^{2}\log n >> n(\log n)^{10}$ (Multiplying both sides by $n \log n)$

So, $n(\log n )^{10} = o(n^{2}\log n)$ and  $n(\log n )^{10} \neq \Theta(n^{2}\log n)$ (making LHS strictly asymptotically lower than RHS)

Or

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

Option $B$.


edited by
0
is it equal ? how?

 

k! = k * (logn)k-1
79 votes

$$\begin{array}{|l|c|c|} \hline \text {} & \textit{f(n)} & \textit{g(n)} \\\hline \text{$n = 2^{10}$} &  \text{$10 \times 2^{10} \times 2^{10}$} & \text{$2^{10} \times 10^{10}$}\\\hline \text{$n = 2^{256}$} & \text{$256 \times 2^{256} \times 2^{256}$} &\text{$2^{256} \times 256^{10}$}  \\\hline \end{array}$$
As $n$ is going larger, $f(n)$ is overtaking $g(n)$ and the growth rate of $f$ is faster than that of $g$. So, $g(n) = O(f(n))$ and $f(n) \neq O(g(n))$.

B choice. 


edited by
0
If we calculate log(f(n)) and log(g(n)) then we get

log(f(n))= 2*log(n)+log(log(n))= O(log(n));

log(g(n))= log(n)+10*log(log(n))=O(log(n));

Can we say that f(n)=O(g(n)) and g(n)=O(f(n)) ?
0
the answer should be D right?
14
Taking log is not a proper method -- it works for some and fails for others.
0

ok sir thank you, and can u please reply to my question in TOC , i really have doubt in understanding the way to approach it thank you!https://gateoverflow.in/1994/gate2014-2-35

0
@Arjun Sir .Great , taking large values of n is probably the best way to solve such questions in gate , isnt it ?
0

But sir then how to decide what to apply log or not when as you had used log  here

https://gateoverflow.in/664/gate2000-2-17

0

@Bikram

sir can you tell me when would option

d) f(n)=O(g(n)) and g(n)=O(f(n))  will be true ??

9 votes

# First let's do the comparison between f(n) and g(n) 

 

     =>      $n^{2}\log n$     &&     $n(\log n)^{10}$   

     =>     $n\log n$        &&     $(\log n)^{10}$          (Cancel out the $n$ from both side )

     =>       $n$                 &&    $(\log n)^{9}$             (Cancel out the $\log n$ from both side )

     =>      $\log n$           &&      $9\log \log n$       (Take $\log$ both side )

 

Now, it is clear that if you take a large value of n then f(n) is greater than g(n)

=>      $\log n$     >     $9\log \log n$   

 

So, $g(n) =O(f(n))$ and $f(n) \neq O(g(n))$

 

Option B is correct.

0
can we cancel terms while comparing complexity between 2 functions?
0
Yes, you can.
0
example

for $n=10^{10}$

$f(n) =\log_{10}(10^{10}) = 10$

$g(n) =9 *\log_{10}(\log_{10}(10^{10})) = 9*1 =9$

$\Rightarrow f(n)>g(n)$
1 vote
g(n) = O (f (n))

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

c is stand for any constant value, it satisfy one condition of option b so by this way you can get answer ..
0 votes

Reference:Solution of Arjun Sir

Case-I

$f(n)=n^{2} logn$ 

take $n=2^{10}$  So, $f(n)=2^{20} log2^{10}$  

$f(n)=2^{20} $ *10 $

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

take $n=2^{10}$  So, $g(n)= 2^{10}(log2^{10})^{10}$

$g(n)= 2^{10}* 10^{10}$

Case-II

And now take one more value 

take $n=2^{256}$ 

o, $f(n)=2^{512} log2^{256}$  

$f(n)=2^{512} $ *256 $

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

take $n=2^{256}$  So, $g(n)= 2^{256}(log2^{256})^{10}$

$g(n)= 2^{256}* 256^{10}$

Now, main problem is how to check which one is bigger than other.

Just do one simple thing divide each other 

like in case-I , if you'll divide f(n)/g(n) 

f(n)/g(n) = $2^{20} $ *10  / $2^{10}$ * $10^{10}$

f(n)/g(n) = $2^{10} $ *10  / $10^{10}$

f(n)/g(n) = 10240 / $10^{10}$

So, here f(n)< g(n)  , f(n) = O(g(n))

 

Now Case-II,

f(n)/g(n) = $2^{512} $ *256  / $2^{256}$ * $256^{10}$

f(n)/g(n) = $2^{256} $ *256  / $256^{10}$

Here, you can simply use Scientific calculator during GATE exam, and you will see quotient is >0.

So, here f(n)> g(n)  , g(n) = O(f(n)) and you can find n where f(n) always greater than g(n)

So, Option B

0 votes

Hope this helps :)

0 votes

f(n) = n2logn; g(n) = n(logn)10
Cancel nlogn from f(n), g(n)
f(n) = n; g(n) = (logn)9
n is too large than (logn)9
So f(n)! = O(g(n)) and g(n) = O(f(n))

So option B

–4 votes
ans is A.

for n=2 : f(n)=4, g(n)=2

for n=3 : f(n)=14, g(n)=300
15
For asymptotic notations, you should always check for large values of n.
Answer:

Related questions

33 votes
4 answers
1
7k views
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort? $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n!)$
asked Sep 14, 2014 in Algorithms Kathleen 7k views
22 votes
2 answers
2
2.5k views
Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$. The ... tree unique over all possible minimum spanning trees of a graph? Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?
asked Sep 15, 2014 in Algorithms Kathleen 2.5k views
28 votes
7 answers
3
6.3k views
Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadth-first traversal, which ... statements is correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above
asked Sep 15, 2014 in Algorithms Kathleen 6.3k views
20 votes
2 answers
4
1.9k views
Consider the following grammar with terminal alphabet $\Sigma =\{a,(,),+,* \}$ and start symbol $E$. The production rules of the grammar are: $ E \rightarrow aA$ $ E \rightarrow (E)$ $A \rightarrow +E$ $A \rightarrow *E$ $A \rightarrow \epsilon $ Compute the FIRST and FOLLOW sets for $E$ and $A$. Complete the LL(1) parse table for the grammar.
asked Sep 15, 2014 in Compiler Design Kathleen 1.9k views
...