Understanding Algorithm Efficiency: From Big-O to Empirical Analysis

An algorithm is a finite sequence of instructions for solving a problem. In this post, I’m assuming some basic programming knowledge, but I’ll explain the algorithm-analysis concepts as we encounter them.

Analysis is the separation of a whole into components for individual study, but when talking about analysis of algorithms we are referring to the investigation of an algorithm’s efficiency when it comes to its running time and memory usage. We focus on those two aspects of algorithms because unlike an algorithm’s generality and simplicity, its efficiency is more precisely quantifiable. Although modern computers have become dramatically faster and gained much more memory, efficiency still matters because the resources required by an algorithm can grow rapidly as its input grows.

How Do We Measure Algorithm Efficiency?

In the early days of computing both time and space used to be extremely expensive resources. After years of constant technological innovations, the speed and memory size of computers have increased by manyfold, making the amount of extra space required by an algorithm less of a concern. However, this doesn’t eliminate the problem of rapidly growing runtime of an algorithm as the input size grows, and is why the computer science field tends to focus on time efficiency.

Almost all algorithms need more time to run as the input size grows larger. So one way we analyze an algorithm’s efficiency is as a function of its input size.

We also need to measure the run time of said algorithm. We could measure it using a standard unit of time like seconds or milliseconds. The problem with taking this approach is that now we would depend on the speed of the particular computer, the quality of the program implementing the algorithm and the compiler generating the machine code, and being able to clock the actual runtime of the program. We want a way to measure an algorithm’s efficiency that doesn’t depend on these factors.

A common approach is to identify the part of the algorithm that contributes the most to the total running time, also called the basic operation, and count how many times that basic operation is executed. The basic operation can often be identified as an operation in the algorithm’s innermost loop that contributes substantially to its total running time. For most sorting algorithms, for example, the basic operation is the part that compares elements of a list. For algorithms solving mathematical problems, the basic operation may instead be an arithmetic operation such as division, multiplication, addition, or subtraction.

The formula for the running time of a program implementing an algorithm on a computer is

$T(n) ≈ Cₒₚ C(n)$

$n$ is the input size

$Cₒₚ$ is the execution time of the algorithm’s basic operation on a particular computer

$C(n)$ is the number of times the basic operation is executed by the algorithm

But when analyzing efficiency, we’re usually less interested in the exact number of times the basic operation runs, and more interested in how quickly that number grows as the input size becomes very large. This is called the order of growth, or growth rate, of an algorithm. An algorithm whose running time grows linearly as its input grows, for example, will scale very differently from one whose running time grows quadratically.

Finally, one thing to consider is that two inputs of the same size don’t necessarily require the same amount of work to process. Depending on the algorithm and the particular input, the basic operation may be executed a different number of times even when the input size is the same. This is why we sometimes analyze the best-case, worst-case, and average-case efficiency of an algorithm separately.

Understanding Big-O, Big-Omega, and Big-Theta

As we said earlier, we focus on the order of growth of the number of times an algorithm’s basic operation executes when analyzing its efficiency. When comparing algorithms based on their orders of growth, we use three notations: $O$ (big oh), $Ω$(big omega), and $Θ$(big theta).

Let’s say that a function $t(n)$ is the running time of an algorithm, and $g(n)$ is a function to compare the growth rate of that algorithm as the input $n$ goes to infinity.

$O(g(n))$ is the set of all functions with a lower or same order of growth as $g(n)$, to within a constant multiple as $n$ goes to infinity.

So when we say that $t(n)$ has $O(g(n))$ we mean it belongs to the set of functions with a lower or same order of growth as $g(n)$. Mathematically that’s $t(n) ∈ O(g(n))$.

$Ω(g(n))$ is the set of all functions with a higher or same order of growth as $g(n)$, to within a constant multiple as $n$ goes to infinity.

Again, $t(n)$ having $Ω(g(n))$ means it belongs to the set of all functions with a higher or same order of growth as $g(n)$, or $t(n) ∈ Ω(g(n))$.

$Θ(g(n))$ is the set of all functions with the same order of growth as $g(n)$, to within a constant multiple as $n$ goes to infinity.

$t(n)$ having $Θ(g(n))$ means that it’s part of the set of all functions with the same order of growth as $g(n)$, denoted $t(n) ∈ Θ(g(n))$.

So if $t(n) = 100n + 5$, then it is accurate to say $t(n) ∈ O(n)$, but it’s also valid to say $t(n) ∈$ $O(n²)$, since $t(n)$ has a lower order of growth than $n²$. However, $O(n)$ gives us a tighter upper bound on its growth.

We can be even more precise and say $t(n) ∈ Θ(n)$, since $t(n)$ has the same order of growth as $n$.

Analyzing the Time Efficiency of Non-Recursive Algorithms

A non-recursive algorithm performs its work without calling itself, while a recursive algorithm solves a problem by calling itself on smaller instances until it reaches a base case. Let’s apply what we’ve learned above and determine the time efficiency of the following non-recursive algorithm.

max = A[0]

for i = 1 to n - 1:
    if A[i] > max:
        max = A[i]

return max

The algorithm is finding the maximum element of an array.

We have an array of $(n)$ elements. The algorithm starts with the first element as max, then walks through the remaining elements. Every time through the loop, it compares the current element against max.

The input size would be the number of elements in the array, so $n$.

There are two operations in the loop: the comparison A[i] > max and potentially assigning A[i] to max. Because the comparison is executed on every repetition and the assignment is not, the comparison is the basic operation.

Now let’s say the array has 5 elements:

$[A0, A1, A2, A3, A4]$

$A0$ initializes max.

Then we compare:

$A1 → max$
$A2 → max$
$A3 → max$
$A4 → max$

Four comparisons.

For ($n$$=5$), that’s ($5-1=4$).

For arbitrary $(n)$, that’s ($n-1$).

So $C(n) = n – 1$.

As $n$ grows, the $-1$ doesn’t affect the order of growth, so $C(n) \in \Theta(n)$. The algorithm therefore has linear time efficiency.

Notice that the comparison happens $n-1$ times regardless of the values stored in the array. Because the number of executions depends only on the input size and not on the contents of the input, we don’t need to analyze separate best, average, and worst cases for this basic operation.

The general process for analyzing non-recursive algorithms is as follows:

1. Determine the input size. What does $n$ represent?
2. Identify the basic operation. What operation contributes most to the algorithm’s work?
3. Determine what affects its execution count. Does it depend only on $n$, or also on the particular input? If the input matters, we may need best-, average-, and worst-case analysis.
4. Express the number of executions as a function of $n$. This gives us $C(n)$
5. Determine its order of growth. Simplify that function asymptotically to determine the algorithm’s efficiency class

Analyzing the Time Efficiency of Recursive Algorithms

Now we’ll apply what we learned to a recursive algorithm. We’ll do that with factorials. Let’s look at the function $F(n) = n!$ for an arbitrary nonnegative integer $n$. We know that$n! = 1 * … * (n – 1) * n = (n-1)! * n$ for $n >= 1$ and that $0! = 1$ so we can write the following recursive algorithm

if n = 0 return 1

else return F(n - 1) * n

The input size for this algorithm is $n$.

The basic operation of the algorithm is multiplication.

Let’s denote the number of times the basic operation is executed with $M(n)$.

Now let’s say $n = 4$ and trace what happens.

We start with:

$F(4) = F(3) * 4$

But before we can multiply by 4, we first have to compute $F(3)$. That call needs $F(2)$, which needs $F(1)$, which eventually needs $F(0)$:

$F(4)→F(3)→F(2)→F(1)→F(0)$

Once $n = 0$, we hit the base case and return 1. There is no multiplication at $F(0)$. The recursive calls can then return back the chain, performing one multiplication at each level:

$F(1)= 1 * 1$

$F(2)= 1 * 2$

$F(3)= 2 * 3$

$F(4)=6⋅4$

As we can see, for $F(4)$ , the basic operation is executed 4 times.

Let’s try to come up with a formula for $M(n)$ with this. The math we did above with $n = 4$ shows us that every call with $n > 0$ has to compute $F(n -1)$ and then perform one additional multiplication. This gives us

$M(n) = M(n – 1) + 1$

Unlike the function, $C(n)$, we found for non-recursive algorithms earlier, $M(n)$ is being defined in terms of a smaller instance of itself. This is called a recurrence relation.

Now let’s solve the function we came up with for $M(n)$ by repeatedly substituting that smaller instance until we see a pattern:

$M(n)=M(n−1)+1$

Since

$M(n−1)=M(n−2)+1$

We get

$M(n)=[M(n−2)+1] +1 = M(n-2)+2$

And since

$M(n−2)=M(n−3)+1$

We get:

$M(n)= [M(n-3) + 1]+2 = M(n-3)+3$

The emerging pattern is

$M(n) = M(n-i)+i$

Eventually the recursion reaches its base case, where $n=0$.

When $n=0$, no multiplication happens. If we take the function $M(n) = M(n-i)+i$, what would have to be true about $i$ for $M(n-i)$ to give us the number of multiplications at the base case specifically, 0?

For $n−i=0$, $i$ must equal $n$. Substituting $i=n$ into our pattern gives:

$M(n) = M(n-n)+n$

$M(n)=M(0)+n$

$M(n) = n$

Therefore, the number of multiplications grows linearly with the input size:

$M(n) ∈ Θ(n)$

So even though factorial is being calculated recursively, this particular recursive algorithm still has linear time efficiency.

The process is actually very similar to analyzing a non-recursive algorithm. We still determine the input size, identify the basic operation, count how often that operation executes, and determine its order of growth. The main difference is that with a recursive algorithm, the execution count can itself be recursive, so we may first need to set up and solve a recurrence relation.

So the general process for analyzing recursive algorithms is

1. Determine the input size. Decide which parameter represents the size of the input.
2. Identify the basic operation. Figure out which operation we’re going to count when analyzing the algorithm.
3. Determine whether different inputs of the same size can cause different numbers of executions. If they can, we may need to analyze the best, worst, and average cases separately.
4. Set up a recurrence relation. Express the number of times the basic operation executes in terms of a smaller instance of the problem, and identify the base case.
5. Solve the recurrence relation and determine its order of growth.

In our factorial example, $n$ was our input size, multiplication was our basic operation, $M(n)=M(n-1)+1$ was our recurrence relation, $M(0)=0$ was our base case, and solving the recurrence gave us $M(n)=n$, which means the algorithm has linear time efficiency.

Empirical Analysis: Measuring How Algorithms Actually Perform

Although mathematical analysis can be applied to many algorithms, some algorithms are hard to analyze mathematically with precision and certainty. We must then approach those cases differently.

First we must understand why we’re not analyzing the algorithm mathematically. There are several reasons we might want to study an algorithm experimentally. We may want to test a theoretical claim about its efficiency, compare several algorithms that solve the same problem, compare different implementations of the same algorithm, develop a hypothesis about its efficiency class, or measure how a particular implementation performs on a particular machine.

Understanding why we’re analyzing an algorithm this way helps us determine how we will measure its efficiency.

We could add a counter where the basic operation is in a program that implements the algorithm so we can see how many times the basic operation is being executed. If the basic operation is being executed in more than one place, make sure the counter is in all those places so all executions of the basic operations are accounted for.

We could also time the program implementing the algorithm in question, either by using a system’s command, such as the time command in UNIX, or getting the system time right before a part of a program starts and just after the part is completed and then calculating the difference. This approach might be less accurate so we should take that into account since, by the nature of the approach, you might get different results on repeated runs of the same program with the same inputs.

Once we decide how we will measure the efficiency of an algorithm we then decide what our input(s) should be, what the input size or range should be, etc. Choosing the inputs is important because our results are only as useful as the sample we test. We need to decide what input sizes to use and whether we should test multiple inputs of the same size. If an algorithm can behave differently for different inputs of the same size, testing only one could give us a misleading picture of its performance.

The input sizes can follow a pattern, such as increasing by a fixed amount or doubling each time, or they can be chosen randomly within a range. Using a pattern can make the results easier to analyze. For example, if we double the input size each time, we can compare $M(2n)$ to $M(n)$ and observe how quickly our measured count or running time grows.

We may also need to randomly generate the actual inputs used in our experiment. Computers generally generate pseudorandom numbers rather than truly random numbers, meaning the values are produced by an algorithm from an initial value called a seed.

Once we have our inputs, we run the algorithm, record the measurements, and analyze the results. We can put the measurements in a table or plot them on a scatterplot with the input size $n$ on one axis and the measured operation count or running time $M(n)$ on the other.

The shape and growth of the measurements can then give us evidence about the algorithm’s efficiency class. For example, measurements growing roughly along a straight line suggest linear growth, while a curve that grows increasingly steep may suggest a higher order of growth. We can also compare ratios such as $M(2n)/M(n)$ to see how the measured performance changes when the input size doubles.

We can even use the pattern we observe to estimate how the algorithm might perform for inputs we did not test, although predictions outside the range of our experiment should be treated carefully.

This whole process we’ve been going through in this section—choosing what to measure, selecting inputs, running the algorithm, recording the results, and analyzing those results—is called empirical analysis.

Unlike mathematical analysis, where we derive an algorithm’s efficiency from the algorithm itself, empirical analysis measures what actually happens when we run it. Mathematical analysis has the advantage of being independent of a particular computer or experimental sample, but it can be difficult or impractical for some algorithms. Empirical analysis can be applied more broadly, but its results can depend on the inputs we choose and the machine on which we run the experiment.

So the general process for empirically analyzing algorithms is

1. Understand the purpose of the experiment. Decide what question we’re trying to answer about the algorithm’s efficiency.
2. Choose what we’re going to measure. Decide on an efficiency metric $M$ and its measurement unit, such as the number of basic-operation executions or running time.
3. Decide what inputs we’ll test. Choose the characteristics of the input sample, including its sizes, range, and whether multiple inputs of the same size should be tested.
4. Prepare a program that implements the algorithm. If necessary, add the counters or timing measurements needed for the experiment.
5. Generate the sample of inputs. Create the actual inputs on which the algorithm will be tested.
6. Run the experiment and record the results. Execute the algorithm on the sample inputs and collect the measurements.
7. Analyze the data. Look for patterns in how the measured efficiency changes as the input changes and use those results to draw conclusions about the algorithm’s performance.

Algorithm Visualization: Seeing How Algorithms Behave

Besides mathematical and empirical analysis, the third way to analyze algorithms is through algorithm visualization. Algorithm visualization is the use of images to communicate useful information about algorithms such as a visual illustration of an algorithm’s operation, its performance on different kinds of inputs, or its execution speed versus that of other algorithms for the same problem. To do this it uses graphic elements like points, line segments, two- or three-dimensional bars, and more to help us see what is happening as an algorithm operates.

The two kinds of algorithm visualizations are static algorithm visualization, and dynamic algorithm visualization or algorithm animation. Static algorithm visualization shows an algorithm’s progress through a series of still images while algorithm animation shows a continuous, movie-like presentation of an algorithm’s operations. Animation is the more sophisticated option and more difficult to implement.

Algorithm visualization is mainly used for research, learning, and education. It can help us better understand how an algorithm behaves and potentially notice things about its operation that may be difficult to see from the code alone. However, visualization by itself does not give us a concrete measurement of an algorithm’s efficiency or establish its growth rate. Instead, it complements mathematical and empirical analysis by helping us see what the algorithm is actually doing.

Thoughts and Ponderings

Before studying this chapter, I mostly thought about algorithm efficiency in terms of Big-O notation. What I hadn’t appreciated was the larger framework around it: deciding what input size means, identifying a basic operation, counting how often it executes, distinguishing best, average, and worst cases, solving recurrence relations for recursive algorithms, and even testing algorithms empirically when mathematical analysis isn’t practical.

Mathematical analysis, empirical analysis, and visualization aren’t competing ways of looking at algorithms. They answer different questions. Mathematical analysis helps us reason about how an algorithm scales, empirical analysis lets us observe what happens when an implementation actually runs, and visualization helps us see how the algorithm behaves.

I’m still early in Advanced Algorithms, but I already understand much more clearly what we actually mean when we say one algorithm is “more efficient” than another.