Asymptotic behaviour of a couple of special functions (features exponentials and logarithms)

217 Views Asked by At

I'm dealing with a couple of functions: $n \log n$, $( \log \log n)^{ \log n}$, $( \log n)^{ \log \log n}$, $n e^{\sqrt{n}}$, $( \log n)^{ \log n}$, $n 2^{ \log \log n}$, $n^{1+1/( \log \log n)}$, $n^{1+1/ \log n}$, $n^2$.

I want to order them according to their growth rate and express the ordering using asymptotic notation.

Apart from noticing $n^{1+1/ \log n}=n \mathrm e$, I didn't manage to simplify them. Essentially, what I did so far was plugging in large values for $n$ and comparing plots. Like this I came up with a rough asymptotic ordering: $$n e^{\sqrt{n}} \succ n^2 \succ ( \log n)^{ \log n} \succ n^{1+1/( \log \log n)} \succ n \log n \succ n 2^{ \log \log n} \succ n \mathrm e \succ ( \log \log n)^{ \log n} \succ ( \log n)^{ \log \log n}$$ where $\mathrm f(n) \succ \mathrm g(n)$ means that there is $n_0 \in \mathbb N$ such that $\mathrm f(n) > \mathrm g(n)$ for all $n > n_0$. Obviously, this implies $\mathrm g(n) = O(\mathrm f(n))$.

However, what I'm looking for is a little bit more insight. Is it possible to give some meaning to at least some of them? What I'm trying to do right now is relating each term to a common complexity class. Some are obvious. But what about the two smallest terms for example? Are they in $O(\log n)$ or still linear? How can I fand out?

1

There are 1 best solutions below

2
On BEST ANSWER

Your ordering is slightly incorrect, due to the fact that subtle asymptotic differences are frankly difficult to see clearly on the plot. A general advice for this type of problems: when faced with "exponent-heavy" sequences, try comparing logarithms of values instead of values themselves.

For example, let's take a look at $n^2$ and $\left(\log n\right)^{\log n}$. Taking logarithms, we obtain $2 \log n$ and $\log\log n \log n$. Now it's clear why the plot was not very helpful: $\log\log n$ grows unboundedly, but very slowly, and for $n<e^{e^2}\approx 1600$ it's less than $2$.

Similarly, $\left(\log\log n\right)^{\log n}$ is asymptotically bigger than $ne$, since $\log\left(ne\right)=\log n + 1$, but $\log\left(\left(\log\log n\right)^{\log n}\right)=\log n \log \log \log n$. Needless to say, it's only visible for rather large $n$ (roughly for $n \geq 5.1 \times 10^7$). So it's not only not $O\left(\log n\right)$, but not $O\left(n\right)$, either.

The last function - $\left(\log n\right)^{\log \log n}$ - is not linear, but it's not $O\left(\log n\right)$, either, as can be shown by analogous argument.