4 ms·
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?
by SeanLuke 5y ago
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 5y agoIt'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 5y agoGot it. I had missed the little-o.