Computational Complexity

Every question we have asked about cost so far has been about a particular algorithm:

How many steps does linear search take?
How much faster is binary search?
Why is selection sort $O (n^{2})$ ?
How much stack space does recursive Fibonacci use?
Why is DynamicArray.add $O (1)$ amortized?

Those are all questions of algorithm analysis. We start with a specific algorithm and ask how its time or space grows as the input size grows. Since we write the answer in asymptotic notation, this is also called asymptotic analysis.

Algorithm analysis asks how fast a particular algorithm is. Computational complexity asks how hard the problem itself is.

A problem can be solved by many different algorithms. Sorting, for example, can be solved by selection sort in $O (n^{2})$ time, but faster sorting algorithms run in $O (n lo g n)$ time. Once we know that, we can ask whether $O (n lo g n)$ is just the best bound we have found so far, or whether there is some reason sorting cannot be solved faster in general.

That is the kind of question computational complexity studies. It uses the same vocabulary we have been using: time complexity, space complexity, worst-case guarantees, and how work grows with input size. It adds one idea we have not used yet, which is a bound on the problem itself.

When we show that an algorithm solves a problem in $O (n)$ time, we have given an upper bound on the problem. The problem needs at most that much time, because we have an algorithm that solves it in that time. A lower bound is the opposite kind of claim. It says no algorithm can solve the problem faster than a stated growth rate. When the upper and lower bounds meet, we know exactly how hard the problem is.

When we say “this algorithm is $O (n lo g n)$ ”, we are making a claim about one algorithm. When we say “Every (comparison-based) sorting algorithm requires $Ω (n lo g n)$ comparisons in the worst case,” we are making a claim about every algorithm in that category. The $Ω$ there is the notation for a lower bound, the way $O$ is the notation for an upper bound.

Computational complexity also groups problems into broad families. One rough dividing line separates problems that have polynomial-time algorithms, such as $O (n)$ , $O (n^{2})$ , or $O (n^{3})$ , from problems whose best known algorithms take exponential or factorial time, such as $O (2^{n})$ or $O (n!)$ . A polynomial-time algorithm is not always fast in practice. An exponential-time algorithm can still be fine on tiny inputs. But polynomial growth stays manageable up to much larger inputs than exponential growth does.

That dividing line is where the open question P versus NP comes from. Very roughly, it asks about problems where a proposed answer can be checked in polynomial time but where we do not know whether an answer can be found in polynomial time. We will not study P and NP in this course, but the theory behind them starts from the same thing we have been doing here, which is describing how an algorithm’s resource use grows.