Time Complexity

Question

which function will grow faster?

a) x^$\sqrt{x}$ 

b) x!   

Comments

BLUE $\Rightarrow$ x! 

Red $\Rightarrow$ x^√x 

x! grows faster

---

x!=x (x-1) (x-2)....3.2.1=O(x^x)

Now, compare x^x and x^sqrt(x)

x^x will grow faster

---

Take log on both sides..

√xlogx  and log(x!)

log(x!) Can be written as xlogx( you can search the derivation )

So,

√xlogx and xlogx

B is greater..

---

@MiNiPanda   yes youre right , i heard  sometime taking log it can give incorrect result , thats why i avoid using it , since by taking  log it  decreases  the rate of function exponentially , how we will sure that , here rate is not decreased  exponentially

---

It gives incorrect result only when both sides become equal.

In this case if both would have come xlogx then it would have been incorrect to infer that both have same rate of growth. In that case other ways should be followed.

But if they are different then it's okay...

---

like n^2  and n are not theta of each other , but if i took  log  ,  then 2logn and logn are theta of each other  thanks @MiNiPanda 

---

Approximation for logn! $\approx$ (n+1)logn - n

by Srinivasa Ramanujan :o

---

Right Sumit :D

Utkarsh ooh..maybe .. but that again can be approximated to nlogn for asymptomatic analysis..