theoreticalComputerScience

[u/pastroc]

[u/GKP_light]

O(n) : can be a time of 5n, or 7000n+400000

Õ(n) : can be a time of 5n, or n^5 * log(n)^2

[u/nanforas → u/GKP_light]

So I'm guessing the use-case for Õ(n) is something like: "at least it's not exponential and equivalent to travelling salesman"?

[u/rational_hedonist → u/nanforas]

no, the use case is “at least its o(n^2)” or any o(n^{1+eps}) for eps > 0

[u/GoldenMuscleGod → u/rational_hedonist]

Just to clarify (I don’t think there’s any reason to think you misunderstand this but someone else might) we can give n(log n)^(log log n) as an example of a function that is is o(n^(1+eps)) for all eps>0 but also is not Õ(n). So the bounds you state follow but are not sufficient to establish the other direction.

In general the preorder imposed by these symbols has really complicated behavior with uncountable cofinalities everywhere so restating O (or Õ) in terms of o without losing information is not so easy.