Reading

Skiena, The Algorithm Design Manual: sections 2.1–2.5
The course book has a chapter on complexity, but I don't like it much and will rewrite it in the future.

Slides and videos

Complexity, A–D

Note for videos videos A–E: If you think something is weird with the face recording, it's not your computer, but the video. The face recording has a very low framerate. The slide recording (including mouse movements) and sound is unaffected.

Some big picture clarifications

Some of you may be confused about the fancy words in "asymptotic complexity". This is the picture I keep in mind:

Program --[complexity]-> Mathematical function --[order of growth]-> Growth rate

"Asymptotic" is just another word for taking the order of growth.

"Complexity" just means the cost of the program (can be time, space, number of comparisons, ...) expressed as a function of some given parameter. If the parameter does not fully determine the function (maybe there are several cases with the same parameter value, but different cost), we have to say one of worst case, average case, best case. By default, we mean worst case. The precise meaning of "time" and "space" depends on how we model computation, but once we pass to order of growth, it doesn't matter much anymore.

"Growth rate" we express using O-notation. So you have to be confident in that. f ∈ O(g) means there is a constant C such that f(n) ≤ C g(n) for big enough n (after some constant). So, up to a constant factor, g is an upper bound for f asymptotically (as n goes to infinity). Similarly, we have Ω for lower bound and Θ for exact growth rate. Both can be expressed using O (by flipping f and g). O, Ω, Θ are unrelated to worst case, best case, average case (each combination makes sense).

"Amortized" complexity measures not just one execution of the program/operation, but the average cost of a sufficiently long sequence of such operations. You don't have to know the exact definition. Optional details: The best definition is actually using the potential method. It's like adding a battery to the data structure and defining the cost not just as the run time, but run time plus the change in the battery level:

When we insert an element in a dynamic array and we don't have to resize, we charge the battery by a constant amount. The cost is still constant.
When we eventually have to double the capacity, we use all the energy stored in the battery to make up for the linear cost of reallocating the array. The cost is now constant.

To make this work precisely, we define what the battery level should be for any state of the data structure. For size n and capacity c (n ≤ c), it is (2n - c)/c * <cost of reallocating to twice the capacity>. What's important is that the battery level can never be negative.

(Amortized complexity can be combined with each of worst case, average case, best case and each of O, Ω, Θ (asymptotic upper bound, asymptotic lower bound, exact growth rate). For example "Asymptotic average-case amortized complexity". If you can figure out what that means, your understanding is good enough for everything.)

Mentimeter quiz

Results