How useful is Landau notation?

In the context of a new answer to an old question on Computer Science SE and a subsequent chat, I started thinking about how useful Landau notation (also “Big-Oh”) really is. Since I am quite opinionated about the whole thing I thought a blog post would be a better place than Stack Exchange for collecting these thoughts.

To be clear, I have Landau notation as commonly used in algorithm analysis in mind, i. e. something along the lines of

O(f) = \{ g : \mathbb{N} \to \mathbb{N}_0 \mid \exists c > 0, n_0 \in \mathbb{N}.\ \forall n > n_0.\ g(n) \leq c \cdot f(n) \}.

The usual theme you see is that some cost measure (usually running time) is said to be “in O(n^2)” (or some other function). When I write “Landau-bounds” in the sequel I mean the ensemble of O, \Omega and \Theta in the above flavor. You may add o and \omega; they do not change the picture significantly.

Advantages

Alleged Advantages

Problems

Technical

In summary, Landau notation alone is neither useful for predicting the behavior of algorithms in practice with any amount of precision, nor is it useful for comparing algorithms of similar performance.

Cultural

Alternatives

Verdict

Arguably, notation has one purpose and one purpose only: enable effective and efficient communication. Do Landau-bounds really serve this purpose in the context of rigorous algorithm analysis?

I say no. We should use them as little as possible and strive to produce better, more precise results.

Dear readers, did I miss something? Do you agree on the lists but not with my conclusion? Please leave your comments below!


References

  1. [1]

    Salvador Roura: An Improved Master Theorem for Divide-and-Conquer Recurrences, in Automata, Languages and Programming, 1256, eds Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela (Springer Berlin Heidelberg, 1997), 449–459, DOI: 10.1007/3-540-63165-8_201.

  2. [2]

    Ronald L. Graham, Donald E. Knuth, and Oren Patashnik: Concrete Mathematics: a Foundation for Computer Science, 2nd ed. (Addison-Wesley, 1994). ISBN: 0-201-55802-5.

  3. [3]

    Donald E. Knuth: The Art of Computer Programming (1968–20xx).

  4. [4]

    Robert Sedgewick and Philippe Flajolet: An Introduction to the Analysis of Algorithms, 2nd ed. (Addison-Wesley Professional, 2013). ISBN: 032190575X, aofa.cs.princeton.edu.

  5. [5]

    Kalle Rutanen et al.: A General Definition of the O-Notation for Algorithm Analysis. 2015. arxiv.org.


How useful is Landau notation? - January 12, 2016 - Raphael Reitzig