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

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.