The Metaphysics of Big-O Notation - Gregory Bringman

The Metaphysics of Big-O Notation | Companion Article in French

This is a "code critique" posted in the 2016 Critical Code Studies Working Group, on the indebtedness of Big-O notation to the historical calculus. Big-O notation measures the performance of computer algorithms, but the value of this performance is tied to the perceived importance of the mathematical calculus of Leibniz and Newton. See also my article in French on Big-O Notation, Comparison asymptotique


This is "proto-code" for comparing the operating efficiencies of two algorithms or functions, with a longer history in the field of mathematics.

There are two notations : That of Edmund Landau / Paul Bachmann, followed by that of Godfrey Harold Hardy / Paul Du Bois Reymond.

f(x) = O(1), f(x) = O(log n 2), etc...

f(x) ≺ g(1), f(x) ≺ g(log n 2), etc...


Despite the fact that Big-O Notation makes it easy to characterize the speed or efficiency of algorithms by associating these code components to scales of function growth such as logarithmic or factorial, to use this notation completely transparently as if it only represented quantitative measure is to cloud over its origins in historical calculus.

By the time Donald Knuth writes his letter to SIGACT News in 1976, "Big Omicron and Big Omega and Big Theta" his reasons seem less to keep the origins of this notation in the foreground than to facilitate a generic technical application of this notation to problems in computer science. Although Knuth admits that we should have recourse to the notation of Hardy (consisting of the limit-like operators, ≻, ≺, ≍, ∼, ≼, ≽.) any time the notation of Landau is insufficient (the notation that became Big-O), there is a sense in which Knuth is laying out a set of best practices arguing for an optimized use of only O, Ω, Θ, of the Big-O family of notations.

For those who recall that Big-O notation roughly designates efficiency through comparative scales ranging from constant and logarithmic time as the most efficient growth types to geometric and factorial as the least efficient types, a brief review of Ω and Θ is perhaps necessary. Whereas O, or omicron is used to designate the convergence of values towards 0, Ω or omega is used to designate the convergence of values towards infinity, within a given algorithm. Θ, or theta, on the other hand, is used when the range of values in the growth of a function move neither towards 0 nor infinity, but between two finite fixed limits based upon a domain specific attribute or data condition of the algorithm.

So for instance, writing f(x) = O(1) means that the algorithm denoted by f(x) converges in value towards 0 in constant time. Similarly, f(x) = Ω(1) converges in constant time, but towards infinity, and f(x) = Θ(1) means that f(x) has a fixed, finite growth path in constant time. To designate other growth scales, one uses something like log n 2, n + 2, 2^n, and n! for logarithmic, arithmetic, geometric, and factorial, i.e. O(log n 2), O(n + 2), O(2^n) and O(n!), where 2 is a concrete but arbitrary constraint of the algorithm. Analogously, these growth scales are used with omega and theta, i.e. Ω(...), Θ(...).

This notation is fitting for problems in computer science, because the notation of Landau above involves function notation, as if to characterize the growth of a function we might designate that it is simply equivalent to another function, i.e. function f = Ω, or f(...) = Ω(...). In contrast, the notation of Hardy and the French 19th century mathematician Du Bois-Reymond, tied to the same mathematics that resulted in Big-O Notation, is more closely tied to this same mathematics and uses operators instead of functions, ≻, ≺, ≍. So, the notation f(x) ≻ g(x) means that the growth rate of f in relation to g is f(x) / g(x) -> infinity. With the ≺ operator, f(x) / g(x) converges toward 0, and with ≍, is between two finite, fixed limits.

Because Hardy’s and Du Bois-Reymond's notation adopts the terminology of mathematical limits, it more closely represents the early understanding of the historical calculus of Leibniz and Newton. Curiously, there is a strong metaphysical current that animates early calculus, for example, in Leibniz's notion of infinitely small values, which Michel Rolle and Jean d'Alembert both strongly criticized as an absurdity that had no place in 18th Century quantitative mathematics. Even though values converge to 0 in Big-O notation, in Hardy's notation, this convergence to 0 is a direct result of denoting a limit from two finite whole numbers positioned together in fractional notation. Rolle and others were particularly disturbed by the quality touted by both Newton and Leibniz, that in the space of the infinitely small, the movement of a curve towards a limit or tangent results in a mysterious disappearance of the distance between them that paradoxically can only be denoted by a limit of 0/0.

Despite the early criticisms of Rolle and d'Alembert, by the time of the work of Du Bois-Reymond, upon which the work of Hardy is based, the language of theorems for function growth is still tied seemingly to this metaphysics of limits, of the infinitely small. Moreover, that Du Bois-Reymond's work is still couched in a more philosophical or metaphysical language 200 years after Newton and Leibniz can be shown by the fact that Du Bois-Reymond obfuscates the agent of this supposed function growth in his “Théorème général concernant la grandeur relative des infinis des fonctions et de leurs dérivées” (1872), with no need felt to explain why mathematicians are concerned with this asymptotic growth property. Additionally, Hardy, in bringing the work of Du Bois-Reymond to an English-speaking audience, sees himself as greatly clarifying insights that were totally couched in the metaphysical system of Du Bois-Reymond.

The transparent use of Big-O in the software industry among other places, then, has opted out of drawing philosophical conclusions from advanced mathematics. On the one hand, it may be naive to believe that, in the age of high technology, we can do without the applications of calculus, but it is equally naive to believe Big-O can be completely disconnected from drastically different belief systems or theories of value tied to the birth of this calculus. Still there seems to be no room in the software industry to re-channel the philosophical insights that largely qualitatively drove the invention of the calculus. Should we reintroduce the operators of Hardy and Du Bois-Reymond? I'm not actually calling for this move. These operators do seem however to imagistically signify both the problematic space between tangent and curve of calculus proper and the space where mathematical systems of notation break down and necessitate alternative conceits or sign systems, vis-a-vis serious philosophical questioning, reflection and/or critique.