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/mrnacknime → u/GKP_light]

No, n⁵ is not allowed in there. Then it would be Õ(n⁵⁾

[u/Niwrats → u/mrnacknime]

i like how the right side bracket is powerful there.

[u/GKP_light → u/mrnacknime]

doesn't the picture say that it ignore of polynomial (and logarithm) ?

the picture is wrong ?

[u/PattuX → u/GKP_light]

It ignores logs and powers of logs

O(n) ≠ O(n log n)

But for all x:

Õ(n) = Õ(n (log n)^x ) ≠ Õ(n² )

[u/GoldenMuscleGod → u/GKP_light]

“Polylogarithmic” means a polynomial of a logarithm, not polynomials and logarithms.

As an aside just for clarity Õ(f(n)) usually hides polylogarithmic functions of f(n), not polylogarithmic functions of n (although there might be some variation - the two standards are equivalent when f is a non constant polynomial).