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

49 votes

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

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.

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

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

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

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.

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

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

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 ?

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.

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

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