O(1)
< O(log(n))
< O(sqrt(n))
< O(n)
< O(n log(n))
< O(n²)
< O(2ⁿ)
< O(n!)
@0foldcv I don't remember ever seeing this combination of < and O. Is it supposed to mean something different than = O(...)?
@axiom @0foldcv So according to your formulation, if \(S\) is the set of all functions that grow proportionally to \(n\) but with constant of proportionality greater than 1000, and \(T\) is the larger set of linearly-growing functions with constant of proportionality greater than 100, then \(S<T<O(n)\)? Why is this a helpful variation on the existing notation?
@axiom @11011110 Exactly. I used "<" in the sense of "strict subset" (maybe I should have used "⊂").
Saying something like
O(log(n)) = O(n) seems too much of an abuse of notation for my taste (because O(n) = O(log(n)) is false).
Not sure if "=" is always an abuse of notation for Landau symbols, but at least it's convenient for things like f(x) = g(x) + O(x²). In the previous case, I would prefer it meant equivalence.
@0foldcv @axiom My interpretation is that you should think of "= O" as being one piece of notation, to be read as meaning something like "grows at most as quickly as". Because it makes sense that way when it doesn't make sense as a separate equality relation and function-to-set-of-functions operator. That's why I react so negatively when I see things like "< O". You're neither using the standard notation nor using a combination of operations that makes any sense.
@11011110 @axiom I agree with you for statements involving a function on the left hand side, such as f(x) = O(g(x)), as I mentioned before.
But do you not think that it’s confusing to write “O(log(n)) = O(n)”, when what meant is “f(n) = O(log(n)) implies that f(n) = O(n)”?
What notation would you have used for the chain of strict subset relationships in my original post?
This one is interesting too:
∀ a>0, b>1: O(log_b(n)) ⊂ O(nᵃ).