GATE CSE 2011 | Question: 37

Question

Which of the given options provides the increasing order of asymptotic complexity of functions $f_1, f_2, f_3$ and $f_4$?

• $f_1(n) = 2^n$
• $f_2(n) = n^{3/2}$
• $f_3(n) = n \log_2 n$
• $f_4(n) = n^{\log_2 n}$

• A. $f_3,  f_2, f_4, f_1$ 
• B. $f_3, f_2, f_1, f_4$
• C. $f_2, f_3, f_1, f_4$
• D. $f_2, f_3, f_4, f_1$

Answer 1

Answer is $(A)$.

$n \log_2 n < n^{3/2}$ is quite straightforward as $n^{{3}/{2}} = n \times n^{1/2}$ and $\log n < n^{1/2}$ as logarithmic growth is smaller than exponential growth however small be the exponentiation factor.

Also, $n^{3/2} < n^{\log_2 n} $ and $n^{3/2} < 2^n$.

Now only $n^{\log_2 n}$ and $ 2^n$ need to be compared.

Taking $\log$ of both $(\log_2 n)^2$  and $n$,

$n > (\log_2 n)^2$

Hence, $2^n >  n^{\log_2 n} $.

NOTE: We cannot compare two functions for asymptotic growth by taking $\log$ if they are giving constants after $\log$ operation.

Comments

Very Important point of asymptotic growth

---

write one in terms of other like 3= (1.5*2) it will be 1.5^n * 2^n

 

after writing one in terms of other cancel the common terms

2^n (LHS)        1.5^n *2^n (RHS)

both side 2^n gets cancelled so now

 

1(LHS)     1.5^n (RHS)

 

 

SO LHS<RHS

---

The same type of concept asked in

• GATE CSE 2021 Set 1 | Question: 3
• GATE CSE 2017 Set 1 | Question: 04
• GATE IT 2008 | Question: 10

Answer 2

1. $f_1(n) = 2^n$
2. $f_2(n) = n^{3/2} = n^1*n^{1/2} = n\sqrt{n}$
3. $f_3(n) = n \log_2 n$
4. $f_4(n) = n^{\log_2 n}$

$Remark:$
1. f1 is exponential function, which is largest among all.
2. f2 > f3
3. f4 > f3
4. f4 > f2

A is the correct answer!
 
 

Answer 3

There is a concept of Rates of Growth in Calculus.

Definition :-  f(x) <<<  g(x)  as x $\rightarrow$ $\infty$ means growth rate of f(x) is very  slow  as compared to g(x) when x $\rightarrow$ $\infty$  ie. $\frac{f(x)}{g(x)} \rightarrow 0 \, \, as \, \, x\rightarrow \infty$

It is true when f and g are non-negative.

So, we can say that :-

  1) $if \lim_{x\rightarrow \infty } \frac{f(x)}{g(x)} = \infty \, \, then\,\, f(x) >>> g(x)$ ie. growth rate of f(x) is higher than g(x)

                                                        (or)

  2)  $if \lim_{x\rightarrow \infty } \frac{f(x)}{g(x)} = 0 \, \, then \,\,g(x) >>> f(x)$ ie. growth rate of g(x) is higher than f(x)                            

Based on this fact we can say that :-

Rates of Growth of the following functions is :-

lnx << x^p << e^x << $e^{x^{2}}$ for p>0

and Rates of Decay should be :-

$\frac{1}{lnx}$ >> $\frac{1}{x^{p}}$ >> e^-x >> $e^{-x^{2}}$ , p>0

----------------------------------------------------------------------------------

Now , Rates of growth of Running Time of algorithms is same as order of growth of running time of  algorithms. It is already mentioned in Cormen

According to Cormen ,

f(n) is asymptotically larger than g(n) if f(n) = $\omega$ (g(n))

                                               (or)

$if \lim_{n\rightarrow \infty } \frac{f(n)}{g(n)} = \infty \, \, exist \, then\,\, f(n) \,\,becomes\,\, arbitrary \,\, large \,\, as\,\, compared\,\, to\,\, g(n) \,\,as\,\, n \,\,tends \,\,to\,\, infinity $

----------------------------------------------------------------------------------

Now , In this Question ,

On comparing f₂ and f₃

$\lim_{n \rightarrow \infty } \frac{n^{\frac{3}{2}}}{nlogn} = \lim_{n \rightarrow \infty } \frac{n^{\frac{1}{2}}}{logn} , when \,n \neq \infty \,\,$$Now , using \,L'H\hat{o}pital \, Rule , \lim_{n \rightarrow \infty } \frac{n^{\frac{1}{2}}}{logn} = \infty$

I have taken natural log above because it does not matter and we can convert one base to another and then solve. It will give same answer

So, f₂ >>> f₃

Now , On comparing f₁ and f₄ :-

$\lim_{n \rightarrow \infty } \frac{2^{n}}{n^{logn}}$

Since , 2ⁿ = (e^ln2)ⁿ =  e^n*ln2

and n^lnn = (e^{ln n})^{ln n} = $e^{(ln n)^{2}}$

Since , exponential is an increasing function. So, comparing 2ⁿ and n^{ln n} is same as comparing n*ln2 and (ln n)²

So, By using $L'H\hat{o}pital's \, Rule $

$\lim_{n\rightarrow \infty } \frac{n*ln2}{(ln n)^{2}} = \infty$

So, n*ln2 > (ln n)²

 and $\lim_{n \rightarrow \infty } \frac{2^{n}}{n^{logn}}$ = $\infty$

So, now we can say f₁ >>>f₄

Now, these 2 comparison of functions are enough to eliminate options in this question.

Comments

Best answer!

---

Excellent answer Ankit.

This is actually a formally correct answer. All other answers are informal OR “formally” incorrect.

Hope students learn this answer and this technique rather than informal ones.

---

Deepakk Poonia (Dee) Is rigorous mathematics really that important for a master’s course? Don't get me wrong, I understand I will come across it many times, but being bad at it is not going to be a problem right? Interested more in the application/engineering part.
Thanks.

Answer 4

This can be solved easily by taking the large value for n, say, $n=2^{256}$.

$f_1(2^{256}) =2^n= 2^{2^{256}} = 1.15 * 10^{77}$

$f_2(2^{256})= n^{3/2} = (2^{256})^{(3/2)}=2^{384}$

$f_3(2^{256})= nlog_2n=2^{256}log_22^{256}=2^{256}*2^8=2^{264}$.

$f_4(2^{256})=n^{log_2n}=(2^{256})^{256}=2^{65536}$.

$\Rightarrow f_3,f_2,f_4,f_1$ in increasing order of asymptotic complexity.

Answer is (A).