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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 votes

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}$

- $f_3, f_2, f_4, f_1$
- $f_3, f_2, f_1, f_4$
- $f_2, f_3, f_1, f_4$
- $f_2, f_3, f_4, f_1$

+31 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.

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

+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?

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?

+14

+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

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$

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$

+9 votes

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!**

+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 << 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_{2} and f_{3 }

$\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_{2} >>> f_{3}

Now , On comparing f_{1} and f_{4} :-

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

Since , 2^{n} = (e^{ln2})^{n} = e^{n*ln2}

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

Since , exponential is an increasing function. So, comparing 2^{n} and n^{ln 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 f_{1} >>>f_{4}

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,931 questions

52,334 answers

182,382 comments

67,816 users