2 ms·
It means m^(1+eps) for arbitrarily small positive constant epsilon. So you can make it run in time O(m^1.1) but also in time O(m^1.00000001), where the latter w
by tromp 4y ago
It means m^(1+eps) for arbitrarily small positive constant epsilon. So you can make it run in time O(m^1.1) but also in time O(m^1.00000001), where the latter will presumably have a larger constant implied by the O().
The technical reason you can make eps arbitrarily small is that it represent a function of m that tends to 0 as m tends to infinity.
- plopilop 4y agoMhh, while what you are saying is not wrong (though I'm not convinced about the constant thing, given everything is asymptotic), it's a bit imprecise. A more exact formulation would be m^(1+o(1)) is equal to m^(1 + eps(m)) for some eps where eps(m) -> 0 for m -> infty