Follow

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

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(...)?

@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\)

Sign in to participate in the conversation
Mathstodon

A Mastodon instance for maths people. The kind of people who make \(\pi z^2 \times a\) jokes. Use \( and \) for inline LaTeX, and \[ and \] for display mode.