Follow

O(1)

< O(log(n))

< O(sqrt(n))

< O(n)

< O(n log(n))

< O(n²)

< O(2ⁿ)

< O(n!)

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

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?

0-fold cross-validation@0foldcv@mathstodon.xyzThis one is interesting too:

∀ a>0, b>1: O(log_b(n)) ⊂ O(nᵃ).