1.7k 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.7k views
Here for getting quick answer first do minimization on both the sides then apply log on both the sides.

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

First do minimization on both the sides

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

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

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

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

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

Applying L'Hopital rule

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

$= \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}$

So $n(\log n )^{10} = o(n^{2}\log n)$

Or

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

and

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

Option B.

selected by
Impressive ..... Bt for exam purpose taking a big N value will be more effective ... Dont mind ....
$f(n)$ $g(n)$
$n = 2^{10}$ $10 \ast 2^{10} \ast 2^{10}$ $2^{10} \ast 10^{10}$
$n = 2^{256}$ $256 \ast 2^{256} \ast 2^{256}$ $2^{256} \ast 256^{10}$

So, 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
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)) ?
the answer should be D right?
Taking log is not a proper method -- it works for some and fails for others.

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

@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

+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 ..
ans is A.

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

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