The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.5k views

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}$
  1. $f_3,  f_2, f_4, f_1$ 
  2. $f_3, f_2, f_1, f_4$
  3. $f_2, f_3, f_1, f_4$
  4. $f_2, f_3, f_4, f_1$
asked in Algorithms by Veteran (101k points)
edited by | 1.5k views

3 Answers

+30 votes
Best answer
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.
answered by Loyal (9k points)
edited by
+2

{2^n} will be having highest asymptotic complexity. so i think B cannot be answer

0
agreed I'll edit my answer
+1
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?
+11
For substitution, you should use 2-3 values and not just 1. Then only you can know the growth rate.
+1
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
+7 votes

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!
 
 

answered by Boss (40.2k points)
+1 vote

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 << xp << ex << $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 f2 and f3

$\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, f2 >>> f3

Now , On comparing f1 and f4 :-

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

Since , 2n = (eln2)n =  en*ln2

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

Since , exponential is an increasing function. So, comparing 2n and nln n is same as comparing n*ln2 and (ln n)2

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

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

So, now we can say f1 >>>f4

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

answered by Loyal (7.2k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,848 questions
46,814 answers
141,151 comments
59,064 users