in Algorithms edited by
18,498 views
63 votes
63 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?

  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))$
in Algorithms edited by
18.5k views

4 Comments

@vishalshrm539

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

3
3
good and simple one thanks
0
0

7 Answers

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

edited by

1 comment

is it equal ? how?

 

k! = k * (logn)k-1
0
0
93 votes
93 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. 

edited by
by

4 Comments

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

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

0
0

@Bikram

sir can you tell me when would option

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

0
0
20 votes
20 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.

4 Comments

can we cancel terms while comparing complexity between 2 functions?
0
0
Yes, you can.
0
0
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)$
2
2
Canceling out any term from both sides while comparing always works for all types of functions.
0
0
1 vote
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 ..
Answer:

Related questions