HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

What is my error in reasoning about the complexity class $n^{o(1)}$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
reasoningerrorthewhataboutclasscomplexity

Problem

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?

Solution

$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.

Context

StackExchange Computer Science Q#29714, answer score: 7

Revisions (0)

No revisions yet.