Have you ever struggled with Big-O notation? I used to. If I saw "n = O(n^2)", I perceived "n equals O applied to n^2". It took time to train my mind to instead perceive "n is asymptotically less than n^2". It never caused any serious problems, it was just an incredibly annoyance. I used to think I was the problem, but now I realize the notation was the problem. In large part this realization comes from reading "The Design of Everyday Things", which talks about people blaming themselves for the failings of the common objects around them. It's time to face facts: Big-O notation sucks.
There are two main problems with Big-O notation: it looks like an equality (it's not), and the symbols are arbitrary (w.r.t. the rest of math). The first problem is by far the worse. Big-O notation is meant to express an ordering, not an equality. Using an equality to represent an ordering is a travesty of usability. It encourages you to make contradictory proofs like: 1 = O(1), 2 = O(1), therefore 1 = 2. You might as well switch a car's gas and brake pedals. The second problem is a learnability issue. If I know what Big-O means, and I see a Big-Omega, I can't infer what that means. I need to memorize all five symbols (o, O, θ, Ω, ω), and their meaning (Do you know what they all mean?). These problems have real consequences. There are many perpetually renewed questions on CS forums about the notation for asymptotic complexity, instead of about asymptotic complexity itself.
Since Big-O notation is so bad, let's design a replacement. We want to express an ordering, so we will use the standard ordering operators (<, <=, =, >=, >). We want it to look distinct, so we'll modify the operators in some way (eg. prefix them with an @ for asymptotic). That's it! The new notation is:
[F(x) = o(G(x))] === [F(x) @< G(x)]
[F(x) = O(G(x))] === [F(x) @<= G(x)]
[F(x) = θ (G(x))] === [F(x) @= G(x)]
[F(x) = Ω (G(x))] === [F(x) @>= G(x)]
[F(x) = ω (G(x))] === [F(x) @> G(x)]
Do you see how much clearer it makes the whole affair? It is now obvious that we are dealing with an ordering, obvious that [F(x) @<= G(x)] is the opposite of [F(x) @> G(x)], and obvious that [F(x) @= G(x)] is equivalent to [F(x) @<= G(x) and F(x) @>= G(x)]. All of the non-obvious parts have been isolated into the '@' symbol. In fact, I bet the notation just taught some people what little-omega (ω) means.
Here are some examples, using the above notation:
1 @<= 2
1 @= 10000
1 @< n
2*n @<= n
n^2 @<= n^10000
2^n @> n
3^n @> 2^n
Isn't that much nicer than Big-O notation? I hope that something similar to the above will replace Big-O in the future. I'm tired of telling people what Big-Omega means.
As a closing note, I want to point out how awkward the usual asymptotic complexity definitions are. Proving [Ǝc>0,e>0.∀x>e.F(x)<=c*G(x)] is usually a lot harder than proving lim(x to inf)(F(x)/G(x)) converges.
