[SeanLuke]

What does $m^{1 + O(1)}$ time mean exactly? This could be m^5000 for all we knew. How is this almost-linear, and how can it be guaranteed?

[okintheory]

It's little-oh, not Big-Oh (o(1) is not O(1)). Instead $f(n) = o(1)$ means $\lim_{n \to infty f(n)} = 0$. So $m^{1+o(1)}$ is smaller than $m^1.00001$ for large enough m.

[SeanLuke]

Got it. I had missed the little-o.