For cross verification of your answer follow whatever Arun ji has mentioned in his answer.

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?

- $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$
- $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$
- $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$
- $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

### 8 Comments

For cross verification of your answer follow whatever Arun ji has mentioned in his answer.

## 7 Answers

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

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

### 7 Comments

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

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

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