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

+3

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

+1

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

+1

@vishalshrm539

if it is  $\log n^{10}$ then you can do 10 logn but it is not so

0

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

by Active (1k points)
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.

by Veteran (431k points)
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?
+6
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

+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 ..
by Active (4.7k points)
+1 vote

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

by (57 points)
0
can we cancel terms while comparing complexity between 2 functions?
0
Yes, you can.

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

by Active (4.1k points)
ans is A.

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

for n=3 : f(n)=14, g(n)=300
by Loyal (8.1k points)
+14
For asymptotic notations, you should always check for large values of n.