2.1k 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$

edited | 2.1k views

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.
by Loyal (8.7k points)
edited
+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?
+15
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
+1
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$
0

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

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!

by Boss (42.7k points)

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.

by Boss (14k points)
edited

1
2