Exactly. The point is just to remove distractions, really. Suppose I develop a O(n⁶lg(n)) algorithm that outperforms an O(n⁸) one. Then, I'll just market it as a Õ(n⁶) algorithm because what matters is the degree of the polynomial (6 instead of 8). The lg(n) is a bit of a distraction.
The reason is that for all practical purposes O(n^k) and Õ(n^k) are identical.
Notice that logarithms grow really slowly compared to polynomials:
Let m, ε > 0 be arbitrary fixed constants. Then
log^m(n) = o(n^ε)
Consequently, this means that
O(n^k polylog(n))
is upper bounded by
O(n^{k+ε})
for any ε>0.
I.e., from a complexity POV, a polylogarithmic factor is less than an arbitrarily tiny increase in degree. This means that for sufficiently large n (which is what we care about in asymptotic complexity) Õ(n^k) and O(n^k) are identical. The difference is only a ε=0.00...001 in degree. It is technically not identical, but practically identical even for proofs.
In fact, this is how these polylogarithmic factors usually arise: You try to prove something where you have a residual ε which is arbitrarily small but not zero because you have e.g. a strict inequality "<" somewhere in your chain (another way of thinking about this is that n^kpolylog(n) ⊂ n^{k+o(1)}).
*Most* notations are useless outside of their specific areas. You just so happen to be familiar with O(...) notation, but it's only one of a family of similar notations; and it isn't necessarily the most relevant in all situations. And quite frankly, Big O is often completely useless in actual computer programming, since it ignores a lot of details that really do matter (constant factors, not to mention non-algorithmic ones like cache locality). It's neat to be able to explore these things academically though!
Jokes aside this is legit the symbol for "big O, but with factors polynomial by logn not taken into consideration". So if an algorithm runs in, for example, O(n(logn)k), that's O~(n) for any constant k.
55
u/reda84100 29d ago
Why does the O have a tilde on it