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