GATE2001-1.16

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

edited
1
Here for getting quick answer first do minimization on both the sides then apply log on both the sides.

9

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

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

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

$$\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
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 ??

# 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 ..

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

Hope this helps :)

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

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.

Related questions

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!)$
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?
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
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.