Computational complexity with an epsilon

yavanna

What does that mean when there's an [itex] \epsilon[/itex] in the complexity, such as
[itex] O(n^{2+\epsilon}) [/itex] for every [itex] \epsilon >0[/itex]

I like Serena

Welcome to PF, yavanna!

I would tend to take it very literally.
It says the complexity is greater than [itex]O(n^{2})[/itex].
But it is less than for instance [itex]O(n^{2.1})[/itex].

Note that a complexity of [itex]O(n^{3})[/itex] as well as [itex]O(n^{4})[/itex] implies a complexity of [itex]O(n^{3})[/itex].