Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
SeanLuke
on April 25, 2022
|
parent
|
context
|
favorite
| on:
Maximum Flow and Minimum-Cost Flow in Almost-Linea...
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
on April 25, 2022
[–]
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
on April 25, 2022
|
parent
[–]
Got it. I had missed the little-o.
Consider applying for YC's Spring batch! Applications are open till Feb 11.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
