2.4: A Survey of Common Running Times

This chapter looks at different running times of algorithms and cases in which they would be used. It is suggested to look at a new problem by thinking about two kinds of bounds: one on the running time you hope to achieve, and the other on the size of the problem's natural search space - the set of all possible solutions.

Linear Time

In most cases linear time is used for iterating through a collection.

Quadratic Time

Often times quadratic time is used in double for loops or two conditions on a while loop (as seen in the GS algorithm).

Cubic Time

More elaborate sets of nested loops often lead to algorithms that run in O(n^3).

O(n^k) Time

A running time of O(n^k) is obtained for any constant k when searching over all subsets of size k.

Beyond Polynomial Time

Exponential and n! - avoid these.

Sublinear Time

Essentially in order to get algorithms that run at less than O(n), you need to shrink the size of the “active region” while executing the algorithm. For example, binary search cuts the active region in half each time the loop iterates.

This chapter lays down a good basic description of common running times, but I already knew most of it. 8/10