I'm almost sure I understand $o(1)$ (a class of functions that converge to zero in their limit), but the way I understand it, that would seem to imply that functions in $n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

Certainly the limit of $n^{1/n}$ is 1.

But it can't mean that, because the next question (and yes, this is homework) is to find a function in $n^{o(1)}$ such that its limit is infinity.

So clearly I'm making an error in my reasoning. What am I doing wrong?


Your error is to assume that the convergence from the exponent will always dominate the divergence of the base.

As an instructive example, consider the composition $f^g$, where $f(n) = a^n$, $a>1$ and $g(n) = \frac 1n$. As in your example, $f$ diverges and $g$ converges to 0. So your reasoning would imply that $f^g$ converges to 1.
But, as you easily see, $f^g$ actually converges to $a$. (And by choosing $f(n) = a^{n^2}$, you get an example that diverges.)

  • $\begingroup$ This all makes sense, but doesn't the base have to be just n here? $\endgroup$ – harold Sep 6 '14 at 18:25
  • $\begingroup$ I didn't want to solve your homework for you, so I demonstrated the problem with a different base. The same principle applies with base $n$. You only need other functions in the exponent to see the effect. $\endgroup$ – FrankW Sep 6 '14 at 18:33

$n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

You can't take the limit of one part without taking the limit of the other part, that doesn't give any useful information. If you take the limit of both parts, you get $\infty^0$, which is an indeterminate form.

It's easier to reason about exponentials with a constant base. $$n^{o(1)} = e^{o(1) \cdot \ln(n)}$$ This way you can see that what matters is how fast the $o(1)$ function converges to $0$ relative to a logarithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.