Problem Detail: I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L’Hospital rule but I am stuck with infinite derivatives. Can anyone tell me how i can prove this?
Asked By : Sid
Answered By : Yuval Filmus
You can compare ratios of adjacent values: $(n+1)!/n! = n+1$ versus $2^{2^n}/2^{2^{n-1}} = 2^{2^{n-1}}$. Since $n+1leq 2^{2^{n-1}}$ for $n geq 1$, you can prove using mathematical induction that $(n+1)! leq 2^{2^n}$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6075
