5 ms·
o(1) is "little O" notation, where for a function y = o(f), y(x) / f(x) --> 0 as x --> infinity. In other words, y goes to 0 faster than f. In this context, m^(
by themonteray 4y ago
o(1) is "little O" notation, where for a function y = o(f), y(x) / f(x) --> 0 as x --> infinity. In other words, y goes to 0 faster than f. In this context, m^(1 + o(1)) means roughly that you converge to linear time for large m.
- pfdietz 4y agoOr, rather, it grows more slowly than m^(1 + epsilon) for any fixed epsilon > 0. The function m log m is m^(1 + o(1)) but it grows more quickly than linear.
- account42 4y agoI wish we could all collectively agree that using = for the o/O/etc. notations is stupid and stop this. These are sets of functions. f is not equal to the set, it is an element of the set and we already have a well defined notation for that: f ∈ o(...). So use that or use the LateX f \in o(...) if you want to restrict yourself to ASCII. Using = only serves to confuse.
- pvillano 4y ago(some descriptive linguistics) People often think of "=" as "is", when "is" can convey both equality and possession of an attribute. IIRC there was an article about how American kids think "=" means "the answer is" because they first encountered it with equations like 5+5=10. I've also seen people write 2x+5=10 = 2.5, meaning "the answer to the problem 2x+5=10 is 2.5"