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$

Comments

taking log on both function f2, f3 might here result in wrong answer,,, so better to take log and observe as well as take big value and observe ,,  also here  f2 = n*root n  and  f3 = n*logn  clearly f2 > f3

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

will be having highest asymptotic complexity. so i think B cannot be answer

---

agreed I'll edit my answer

---

Here 2^n is the largest which is quite evident as it is exponential in nature.However for the remaining can be replace n for integral powers of 2 and see the results....The ones which will have larger values in comparison to the others will have greater complexity.

Eg:

2^N is largest

N^log2N,N^3/2,Nlog2N

If we replace N by 2^8 we get

N^log2N = 2^8^8=256^8 which is very large value

N^(3/2) =2^8^(3/2)=2^12=4096

Nlog2N=2^8*8=2048

hence 2^N>N^log2N>N^(3/2)>Nlog2N

can we use this methodolgy?

---

For substitution, you should use 2-3 values and not just 1. Then only you can know the growth rate.

---

Can we compare exponential like the way it is done?Just taking a log and exponential becomes linear polynomial.Does this method works always?

If i compare $2^n$ and $3^n$,taking log answer says both are equal ,but these are not asymptotically equal

---

No , This method does not work always.

Logarithmic and exponential are monotonic in nature. It means they preserves the relative order of the given functions.It does not tell correctly about the comparison of asymptotic growth of the given functions because after taking log function gets change.

Suppose if, we have 2 functions $f(n)$ and $g(n)$ and if we know that $f(n) < g(n)$ is true

Then we can say that $log(f(n)) < log(g(n))$ and $e^{f(n)} < e^{g(n)}$ because logarithmic and exponential are strictly increasing functions in algorithmic context of running time and preserves the relative order of the given functions .

here , growth rate of $3^{n}$ is higher than $2^{n}$ and if we take log both sides , then they are not asymptotically equivalent  because if $f$ and $g$ are  asymptotically equivalent or similar i.e. $f\sim g$ as $n\rightarrow \infty$  then $\frac{f}{g} \rightarrow 1$ which is not the case here because $\lim_{n\rightarrow \infty }\frac{ln 3^{n}}{ln 2^{n}} \neq 1$

---

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

please clear this concept with an example

---

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

---

exactly did the same mistake by taking log and compare

---

if we take n=8
than 2^8 = 256
and 8^log8 = 512
 

so option b is correct

---

We cannot compare two functions for asymptotic growth by taking log if they are giving constants after log operation. can any one plz explain this

 

---

ya but gradually 2^n cross nlogn..for bigger values

---

@Akash2211 If after taking log both sides are equal then the actualy functions may or may not be equal. so after taking log if both are equal we cannot say if they are greater or lesser or equal.

Answer 2

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.

---

palashbehra5  not even all the engineers at top mncs are theoretically mathematician !! people who are able to build things scalable, can code at medium level, having unique ideas, communication skills , presence of mind , etc.   lead the world  : )

Answer 3

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

Answer 5

Taking log of all functions:

f1(n) = n

f2(n) = logn

f3(n) = logn

f4(n) = (logn)^2

f1 is greatest and f4 is second greatest

f2(n)=f3(n) (after taking log) hence is can't conclude between them

f2 vs f3

n^(3/2) vs nlogn

n^(1/2) vs logn

f2 is greater

f3,f2,f4,f1 option A

Answer 6

If they are expecting to find an asymptotic complexity functions means
→ Divide functions into 2 categories
1. Polynomial functions
2. Exponential functions
Above 4 functions we have only one exponential function is f1 (n) = 2n . So, It’s value is higher than to rest of the functions.
Substitute log on both sides then we get an ascending order is f3, f2, f4.
Hence option A

Comments

Hey,what would the expression be like if we take log on both sides for f(3)?