Algorithm

Question

Which of the given options provides the increasing order of asymptotic complexity of functions $f1$, $f2$, $f3$ and $f4$?

  $f1(n) = 2^n \\ f2(n) = n^{(3/2)} \\ f3(n) = nlogn \\ f4(n) = n^{(logn)}$

How $n^{3/2}$ is greater than $n^{logn}$

Comments

is the answer

$f_1 > f_4> f_2> f_3 ????$

---

@shipra tressa $n^\frac{3}{2}$ is not greater than $n^{log n}$ I think. May I know what is the answer given for this?

Answer 1

Increasing order of asymptotic complexity of these functions is $f3<f2<f4<f1$.

ie; $nlogn < n^{3/2} < n^{logn} < 2^n $.

Let's see how: To check this, choose a value of $n$ which is positive and a fairly large one.

A power of $2$ is preferred. I am taking $2^{16}$.

$f3 \rightarrow nlog n \Rightarrow$ $2^{16} log (2^{16}) = 2^{16}$ x $2^4 = 2^{20}$

$f2 \rightarrow n^{3/2} \Rightarrow$ $ (2^{16})^{\frac{3}{2}} = 2^{24}$

$f4 \rightarrow n^{log n} \Rightarrow$ $ (2^{16})^{log({2^{16}})} = (2^{16})^{16} = 2^{256}$

$f1 \rightarrow 2^n \Rightarrow$ $2^{(2^{16})} = 2^{65536}$

Comments

given answer is wrong.

substituting the value and finding the answer may sometimes leads to negative marks in GATE.

By the way your substitution calculation is also wrong.

 

$f1=2^n=2^{2^{16}}=2^{65536}\neq 2^{32}$

---

Oops , got messed up with that one. $2^n$ is biggest, and u r correct. I will edit it, may I know why this method is wrong then.

---

Correct order is F1>F4>F2>F3
Can u explain how to compare F2 and F4 without substituting values?

---

That's what I got by substituting values. If there's any better method, would be helpful if someone can post, @Anand. @shipra tressa

I'm a newbie, kind on me expected :-)

---

yes.. here it is... https://gateoverflow.in/2139/gate2011-37

---

@arungate , nice explanation brother..but as Anand  said substituting  the large value may give wrong answer because at  some large input f₁ > f₂ and it is possible that after that large input f₂ > f₁ ..if we find intersection point(s)  of both functions then only we can say that after intersection point , which function is larger but it is not easy to find intersection point here...we can solve this problem using calculus easily...

---

@ankitgupta.1729 Yes true bro, I think some people may know how to use this method. If you can identify the functions given in choices then this gives quick answer for me. But as you said it may not work if the intersection points are hard to find. Matter of choosing $n > 100000$ when $100000n$ and $n^2$ are given. But not for all functions. :)

---

Also it is all about growth rate

not about how in a certain point functions look like

---

@arungate , bro, 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 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 that GATE2011 question...

 

---

Ok, thanks a lot for the explanation @ankitgupta.1729.

---

@ankit

another point

according to cormen "we cannot compare the functions $n$ and $n^{1+sinn}$ using asymptotic notation, since the value of the exponent in $n^{1+sinn}$ oscillates between $0$ and $2$, taking on all values in between.."

Similar case happens for $n^{logn}$ too right?

---

@srestha , no. In n^logn  , both n and logn are strictly increasing increasing function, so overall n^logn is also increasing. we can check it by graph by putting values of n...but graph of sin n oscillates. sometimes increasing and sometimes decreasing. so we don't know the asymptotic nature when n tends to infinity.

(or)

if we apply the above definition of these non-negative functions, then $\lim_{n\rightarrow \infty } sinn$ does not exist   . but $\lim_{n\rightarrow \infty } logn = \infty$ . Now we can't apply L'Hopital's rule because     then $\lim_{n\rightarrow \infty } cosn$ does not exist. and no other trick will work because we don't know which particular value it is going to...

.................................................................

In algorithms , n and f(n) are always non-negative and f(n) should be monotonically increasing function of running time because when input size increases then machine will take more time to process it. so it can't be decreases.