Real World Asymptotic Complexity

Without a doubt, asymptotic analysis is the most important tool in any algorithm designer’s toolbox. It provides a conceptual framework for divining the runtime of an algorithm without executing it. Many of the field’s advancements would not have been possible without it. Regardless, please heed these words of caution: anything taken to an extreme has deleterious effects. It’s easy to obsess over asymptotic complexity (and performance by extension) as it is the focal point of the study of algorithms. However, the very core of software engineering is managing trade-offs. Overweighting a single variable is to be naive of reality. Asymptotic complexity is a data point for accessing the utility of an algorithm, it is not the whole story. The purpose of this page is to provide the reader with a wholistic view of algorithmic analysis.

Principal of Parsimony

In other scientific domains, the concept of simplicity is a given. Albert Einstein is quoted as saying, “everything should be made as simple as possible, but not simpler.1” The sciences even have a term for the concept: the principal of parsimony (aka law of parsimony or Occam’s razor). Roughly defined, it is “the principle that the most acceptable explanation of an occurrence, phenomenon, or event is the simplest, involving the fewest entities, assumptions, or changes.”2 For algorithms, this means the best implementation is the simplest code, that meets all business needs, involving the fewest entities3.

The principal of parsimony implies that a software professional’s first and foremost responsibility is to deliver the simplest possible solution that meets the business need. Sometimes meeting business need entails squeezing out every last ounce of performance. However, that is not typically the case. Pragmatism is the key to writing successful software. For those who doubt the veracity of this claim, consider this. Donald Knuth literally wrote the book on algorithmic analysis4 and there is no greater authority on the subject. The following quote comes directly from his writings5.

Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.(emphasis added) - Donald Knuth

Much “blood and ink have been spilt” on the merits of software simplicity. A full treatment of the subject is well beyond the scope of this work. It’s sufficient to say, if you must obsess over a software metric, the most appropriate metric is pragmatism. The result of pragmatism is the tenacious pursuit for value. Value is roughly defined in the equation below.

The more complex a solution, the lower its value. To firm this up, consider a fictitious example scenario. Suppose you are tasked with creating an algorithm capable of identifying the two closest objects in a two-dimensional plane. The algorithm below, which has a quadratic runtime ($\Theta(n^2)$), is simple and effective.

\begin{algorithm}
\caption{Brute Force Closest Pair}
\begin{algorithmic}
\REQUIRE $A$ = set of 2-tuples representing $x$ and $y$ coordinates on a plane having $\vert A \vert \geq 2$
\OUTPUT $\min_{(p1, p2) \in A}{\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}}$
\FUNCTION{closestPairBruteForce}{A}
    \STATE min $\gets$ \CALL{distance}{$A_0$, $A_1$}
    \STATE min-points $\gets (A_0, A_1)$
    \STATE
    \FOR{$p1 \in A$}
        \FOR{$p2 \in A$}
            \IF{$p1 \neq p2$ and \CALL{distance}{$p1$, $p2$} $\lt$ min}
                \STATE min $\gets$ \CALL{distance}{$p1$, $p2$}
                \STATE min-points $\gets (p1, p2)$
            \ENDIF
        \ENDFOR
    \ENDFOR
    \STATE
    \RETURN min-points
\ENDFUNCTION
\STATE
\REQUIRE $p1, p2$ = 2-tuples representing x and y coordinates
\OUTPUT $\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}$
\FUNCTION{distance}{$p1$, $p2$}
    \RETURN $\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Is there a more efficient solution? The answer is yes! The algorithm below is “linearithmic”6 ($\Theta(n \log_2{n})$). Don’t get distracted trying to thoroughly understand it as it is explained on a different page. However, take a few minutes to appreciate the complexity.

\begin{algorithm}
\caption{Closest Points}
\begin{algorithmic}
\REQUIRE $A$ = set of 2-tuples representing $x$ and $y$ coordinates on a plane having $\vert A \vert \geq 2$
\OUTPUT $\min_{(p1, p2) \in A}{\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}}$
\FUNCTION{closestPoints}{A}
    \STATE $Ax \gets$ A sorted by $x$ coordinate
    \STATE $Ay \gets$ A sorted by $y$ coordinate
    \RETURN \CALL{recursiveClosestPoint}{$Ax$, $Ay$}
\ENDFUNCTION
\STATE
\REQUIRE $Ax$ = set of 2-tuples representing $x$ and $y$ coordinates sorted by $x$ corrdinate
\REQUIRE $Ay$ = set of the same 2-tuples in $Ax$ sorted by $y$ coordinate
\REQUIRE $Ay$ = list of the same points in $Ax$ sorted by y coordinate
\OUTPUT $\min_{(p1, p2) \in Ax}{\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}}$
\FUNCTION{recursiveClosestPoint}{$Ax$, $Ay$}
    \STATE $n \gets \vert Ax \vert$
    \STATE
    \IF{n $\leq$ 3}
        \RETURN \CALL{closetPairBruteForce}{Ax}
    \ENDIF
    \STATE
    \STATE half $\gets \Bigl\lfloor \frac{\vert Ax \vert}{2} \Bigl\rfloor$
    \STATE left-x $\gets \{Ax_0...Ax_{half}\}$
    \STATE right-x $\gets \{Ax_{half +1}...Ax_{n-1}\}$
    \STATE left-y $\gets \emptyset$
    \STATE right-y $\gets \emptyset$
    \STATE
    \STATE mid $\gets Ax_{half}$
    \STATE mid-x $\gets \text{mid}_x$
    \FOR{$i \in Ay$}
        \IF{$i_x \leq$ mid-x}
            \STATE left-y $\gets \text{left-y} \cup \{i\}$
        \ELSE
            \STATE right-y $\gets \text{right-y} \cup \{i\}$
        \ENDIF
    \ENDFOR
    \STATE
    \STATE smallest-left $\gets$ \CALL{recursiveClosestPair}{left-x, left-y}
    \STATE smallest-right $\gets$ \CALL{recursiveClosestPair}{right-x, right-y}
    \STATE
    \STATE delta $\gets \min\{\text{smallest-left}, \text{smallest-right}\}$
    \STATE smallest-split $\gets$ \CALL{closestSplitPair}{Ax, Ay, delta}
    \STATE
    \RETURN $\min\{\text{delta}, \text{smallest-split}\}$
\ENDFUNCTION
\STATE
\REQUIRE $Ax$ = set of 2-tuples representing $x$ and $y$ coordinates sorted by $x$ corrdinate
\REQUIRE $Ay$ = set of the same 2-tuples in $Ax$ sorted by $y$ coordinate
\REQUIRE delta = minimum distance between items in Ax and Ay
\OUTPUT $\min_{(p1, p2) \in Ax}{\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}}$
\FUNCTION{closestSplitPair}{$Ax$, $Ay$, delta}
    \STATE n = $\vert A \vert$
    \STATE half $\gets \Bigl\lfloor \frac{\vert A \vert}{2} \Bigl\rfloor$
    \STATE mid $\gets Ax_{half}$ 
    \STATE $\bar{x} \gets \text{mid}_x$ 
    \STATE $S \gets \emptyset$
    \STATE max-x $\gets \bar{x}$ + delta
    \STATE mix-x $\gets \bar{x}$ - delta
    \FOR{$p \in Ay$}
        \IF{$p_x \gt$ min-x and $p_x \lt$ max-x}
            \STATE $S \gets S \cup \{p\}$
        \ENDIF
    \ENDFOR
    \STATE smallest-split $\gets \infty$
    \FOR{i $\gets$ 0 to $\vert S \vert - 1$}
        \FOR{j $\gets$ i + 1 to $\min\{i + 7, \vert S \vert\}$}
            \IF{\CALL{distance}{$S_i$, $S_j$} $\lt$ smallest-split}
                \STATE smallest-split $\gets$ \CALL{distance}{$S_i$, $S_j$}
            \ENDIF
        \ENDFOR
    \ENDFOR
    \RETURN smallest-split
\ENDFUNCTION
\STATE
\REQUIRE $p1, p2$ = 2-tuples representing x and y coordinates, $p=(x,y)$, with x and y coordinates
\OUTPUT $\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}$
\FUNCTION{distance}{$p1$, $p2$}
    \RETURN $\sqrt{(p2_x - p1_x)^2 + (p2_y - p1_y)^2}$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Comparing the algorithms, it’s not immediately obvious but Algorithm 2 is actually more performant. However, it has considerably higher implementation and maintenance costs while Algorithm 1 is more malleable. Furthermore, Algorithm 2 is close to incomprehensible without commentary. The only reasonable justification for using Algorithm 2 is in the case where the performance boost provides a competitive advantage that offsets the complexity costs. The performance deficit is likely unnoticeable with meagerly sized inputs or rare invocations. It is advisable to start with the simplest algorithm and only upgrade in the event of a noticeable efficiency shortfall.

Key Takeaways

  • The principal of parsimony implies that a software professional’s first and foremost responsibility is to deliver the simplest possible solution that meets the business need.
  • Pragmatism is a crucial component of designing and writing successful software.
  • $\text{value} = \frac{\text{utility}}{\text{complexity}}$
  • The best strategy is to start with the simplest implementation and upgrade only in the event of a noticeable performance deficit.

Constants Matter!

The Asymptotic Analysis section made it clear that growth rate is the most important runtime component. While this is true, that doesn’t mean that the constants and lower order terms are wholly irrelevant. To demonstrate, consider the case of matrix multiplication. Recognize that it is an extreme example; regardless, it demonstrates the concept beautifully.

The straightforward algorithm, shown below, is $\Theta(n^3)$. Again, do not attempt to master the algorithms on this page just yet as they receive full treatment later on. Take a few minutes to appreciate the complexity or rather the lack thereof.

\begin{algorithm}
\caption{Square Matrix Multiplication}
\begin{algorithmic}
\REQUIRE $A,B$ = $n \times n$ matrices
\OUTPUT $A \times B$
\FUNCTION{squareMatrixMultiply}{$A,B$}
	\STATE $n \gets$ size of matrices
	\STATE $C \gets n \times n$ matrix
	\FOR{$i \in \{1,2,...n\}$}
		\FOR{$j \in \{1,2,...n\}$}
			\STATE $C_{i,j} = 0$
			\FOR{$k \in \{1,2,...n\}$}
				\STATE $C_{i,j} = C_{i,j} + A_{i,k} \times B_{k,j}$
			\ENDFOR
		\ENDFOR
	\ENDFOR
	\RETURN $C$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Now consider Strassen’s matrix multiplication algorithm as shown below which has a runtime of $\Theta(n^{2.8})$. Contemplating asymptotic complexity in a vacuum would lead one to assume that this is a superior algorithm in all cases. However, the constants hidden by the notation are unusually high. Even with a carefully tuned implementation, a performance gain isn’t obvious with matrices smaller than $1024 \times 1024$.

\begin{algorithm}
\caption{Strassen Matrix Multiplication}
\begin{algorithmic}
\REQUIRE $A,B$ = $n \times n$ matrices where $n$ is a power of 2 (4, 8, 16, 32,...) and $n \geq 4$ 
\OUTPUT $A \times B$
\FUNCTION{strassenMatrixMultiply}{$A,B$}
	\STATE $n \gets$ size of matrices
    \IF{$n = 1$}
        \RETURN $A_{1,1} \times B_{1,1}$
    \ENDIF
    \STATE $\left( \begin{matrix} A & B \\ C & D \end{matrix} \right) \gets \text{submatrices of} \; A$
    \STATE $\left( \begin{matrix} E & F \\ G & H \end{matrix} \right) \gets \text{submatrices of} \; B$
    \STATE $S_1 \gets$ \CALL{strassenMatrixMultiply}{$B - D, G + H$}
    \STATE $S_2 \gets$ \CALL{strassenMatrixMultiply}{$A + D, E + H$}
    \STATE $S_3 \gets$ \CALL{strassenMatrixMultiply}{$A − C, E + F$}
    \STATE $S_4 \gets$ \CALL{strassenMatrixMultiply}{$A + B, H$}
    \STATE $S_5 \gets$ \CALL{strassenMatrixMultiply}{$A, F − H$}
    \STATE $S_6 \gets$ \CALL{strassenMatrixMultiply}{$D, G − E$}
    \STATE $S_7 \gets$ \CALL{strassenMatrixMultiply}{$C + D, E$}
    \RETURN $\left( \begin{matrix} S_1+S_2−S_4+S_6 & S_4−S_5 \\ S_6 + S_7 & S_2−S_3+ S_5−S_7 \end{matrix} \right)$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}

Strassen’s algorithm is useful in practice; unfortunately, the same cannot be said for all algorithms. For instance, the Coppersmith–Winograd matrix multiplication algorithm has a runtime of $O(2^{2.374})$; however, it has no practical purpose. The constants are so massive that there is no known terrestrial dataset large enough to take advantage of the improved asymptotic runtime. Algorithms such as this are known as galactic algorithms7.

Key Takeaways

  • In practice, the constants hidden by asymptotic notation can be large enough to render algorithms with higher complexity preferable.

Context Matters

The underlying message of the previous sections is that context matters. There are no absolutes. The best alternative is rarely clear and it’s always different depending on the situation in which it is applied. Asymptotic analysis typically addresses the general case. It’s up to you, as a software professional, to evaluate your specific situation. Below are a few considerations above and beyond algorithmic complexity.

  • It may be possible to manipulate your data to take advantage of a best-case runtime ($\Omega$) rather than the worse-case runtime ($O$).
  • It may be possible to parallelize computation thus raising the total number of requisite machine cycles while lowering the time as measured by a clock.
  • Memory consumption may be more important than runtime in some contexts.
  • Machine architecture can have a huge impact on actual runtime.

Above all, understand that the intricacies that comprise runtime as measured by a clock are staggering. More often than not, microseconds just don’t matter. However, when they are at a premium the only responsible course of action is benchmarking. Test several algorithm variations on representative hardware and data, adjust them, and test again. This seems painfully obvious but it’s all too common for software professionals to neglect the practice. Just to be absolutely clear, never attempt a performance optimization without repeatable benchmarks.

To sum this up, the algorithm with the lowest algorithmic complexity many not be the most performant in a particular application. It is an important data point; however, there are many more to consider.

Key Takeaways

  • There is no best solution. Software professionals have the responsibility to find the solution that best conforms to their context.
  • There are other ways to improve performance beyond reducing asymptotic complexity.
  • Never attempt any performance optimization without clear benchmarks on representative hardware.
  1. A quick Google search revels many sources that attribute this quote to Albert Einstein. The original source of the quote is ambiguous as there are conflicting accounts. 

  2. Oxford Reference: https://www.oxfordreference.com/view/10.1093/oi/authority.20110803100346221 

  3. Technically, the principle of parsimony is a law for describing natural phenomenon and software does not materialize naturally. In this context, it is prescriptive rather than descriptive. 

  4. The Art of Computer Programming (TAOCP) by Donald Knuth is the most influential computer science work ever created. It shaped the industry. It’s next to impossible to find an algorithm textbook that doesn’t reference it. American Scientist listed TAOCP as one of the best twelve physical-science monographs of the century.

    Below is a listing of the lastest volumes of TAOCP as of the time of this writing.

  5. From Donald Knuth’s 1976 paper entitled Structured Programming With goto Statements. It was printed in the book Classics in Software Engineering in 1979. It is available on Amazon using the link below. https://www.amazon.com/dp/0917072146/ref=cm_sw_r_tw_dp_U_x_nZXTEb7NCRCTP 

  6. Linearithmic is a portmanteau of linear and logarithmic meaning $n \log{n}$. Although it violates the “no constants and lower order terms” rule, it’s often useful in practice. The lesson here is that it’s perfectly acceptable to bend the rules for the sake of clarity. 

  7. The name galactic algorithm originates from Richard Lipton and Ken Regan. Due to the highly theoretical nature of the topic, this is it’s only mention on this site. Interested readers can consult the following link for more information: https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/