O(1)
< O(log(n))
< O(sqrt(n))
< O(n)
< O(n log(n))
< O(n²)
< O(2ⁿ)
< O(n!)

· · Web · · ·

This one is interesting too:

∀ a>0, b>1: O(log_b(n)) ⊂ 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 what you really mean is = o(...)?

@11011110 @0foldcv (your formulation is true, and stronger, but not equivalent in meaning)

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

@11011110 @0foldcv I was using existing notation. Strict subset is the natural notion of $$<$$ for sets. This isn't a variation.

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

@11011110 @0foldcv just never use $$= O$$. I always mentally translate it to $$\in O$$ The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!