Time Complexity

In the last chapter we used Big-Oh to describe the amount of work an algorithm does as the input size grows. Linear search is $O (n)$ . Binary search is $O (lo g n)$ . Selection sort is $O (n^{2})$ . The amount of work an algorithm does, as a function of the input size, is called its time complexity. Big-Oh is how we describe it.

Why “time”

We called that work the algorithm’s running time, and we said one algorithm is faster than another when it does less work. But we never measured time. We counted steps: a comparison, an assignment, an array read, an increment. We did that on purpose. A timing in seconds depends on the machine, the language, and whatever else the computer is doing at that moment. A step count depends only on the algorithm and the input.

Step counts still tell us about time because of an assumption we make about the machine. We assume every primitive step takes some fixed amount of time. It does not matter how long, and different steps can take different amounts of time, as long as each one has a fixed cost that does not depend on the input. Under that assumption, doubling the number of steps doubles the running time. The running time is proportional to the step count, so the Big-Oh of the step count is also the Big-Oh of the running time. That is why we can say “time” while counting steps.

Why “complexity”

The word “complexity” here does not mean the algorithm is complicated. Linear search is a simple algorithm of a few lines, and its time complexity is $O (n)$ . Complexity means how much of a resource the algorithm needs, as a function of the input size. Complexity analysis is computing that measure for an algorithm, and comparing algorithms by it. That is what we did in the last chapter, without using the name.

Time is one resource

Time is not the only resource an algorithm uses. Memory is another. When we compared the recursive and iterative binary search, we saw that the recursive version uses more memory, because every recursive call adds a frame to the call stack. The amount of memory an algorithm uses, as a function of the input size, is its space complexity.

There are other resources too. A program that works with files can be measured by the number of reads and writes to disk. A program that sends data over a network can be measured by how much bandwidth it uses. A program on a phone can be measured by how much battery it uses. Each resource gets its own complexity measure. In this course we work with two: time and space.

What a complexity claim specifies

Take the claim “linear search is $O (n)$ .” There are three things it could be more specific about:

Which resource. We meant time. We counted steps, not memory. This is a convention too: a complexity claim that names no resource is about time. When we mean memory, we say space complexity.
Which case. We meant the worst case, where the target is absent and we check every element. Linear search also has a best case, where the target is the first element and we stop after one comparison.
Which scope. We meant a single call to linear search. Some claims are about a sequence of operations instead. Back in the first chapter we saw that add on a dynamic array takes $O (1)$ when the backing array has room but $O (n)$ when it is full and grow has to copy every element into a larger array. To describe the cost of add, it helps to look at many calls in a row rather than one. That kind of claim is called amortized, and we get to it later in this chapter.

This chapter covers each of the three. We start with the case.