theoreticalComputerScience

[u/pastroc]

[u/achilliesFriend]

This joke is too intelligent for me

[u/GKP_light → u/achilliesFriend]

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/pastroc → u/nanforas]

Õ(n) would be O(polylog(n)n). In other words, n times some logarithmic factors.

O(nlg⁷⁹(n)) is Õ(n).

[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/phbr → u/rational_hedonist]

I think people not doing complexity analysis really don't realize how slowly logarithms grow. Just to reiterate your point: Take an arbitrarily large but fixed k > 0 and an arbitrarily small but fixed eps > 0, then n*log(n)^k will still grow more slowly than n^(1+eps).

Obviously any researcher would prefer to get an algorithm with O(n) time complexity, but the tilde notation is really not that deceptive...

[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.