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

Follow

@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?

Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!