GATE CSE 2001 | Question: 1.16

Question

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?

• A. $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$
• B. $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$
• C. $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$
• D. $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

Comments

https://www.youtube.com/watch?time_continue=1&v=g_rNpqWJH4M&feature=emb_logo

---

good and simple one thanks

---

taking log in both functions reduces to
f(n) = log (n^2 * logn)
g(n) = log (n* logn)
clearly f(n) is greater
option B

Answer 1

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

Comments

is it equal ? how?

 

k! = k * (logn)k-1

---

simply remember like in big oh always greater function will come because big o means atmost so among f(n) and g(n) ,f(n) is larger so higher growth rate so option b is correct

---

bhai itne easy question ka ye kya solution bana diye ho , dekh ke darr lagra hai

Answer 2

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

Comments

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

---

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

---

@Bikram

sir can you tell me when would option

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

Answer 3

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

Comments

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

---

Canceling out any term from both sides while comparing always works for all types of functions.

---

best ans among all.

Answer 4

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

Answer 5

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

Answer 6

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