World's most popular travel blog for travel bloggers.

[Solved]: asymptotic growth of n^log log n

, , No Comments
Problem Detail: 

I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ and $2^n$. It seems like it should be closer to the order of $n^n$. Can anyone provide some insight on this.

Asked By : realgenob

Answered By : Yuval Filmus

It could help if you wrote $n^{\log\log n}$ as $2^{\log n\log\log n}$. Then it should be clear that $2^{\log n\log\log n} = o(2^n)$. The morale of this is that the base of an exponent doesn't count as much as the exponent itself.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23496

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback