Run Times

Analyzing run times of algorithms is often done in terms of "Big O" notation. This simplifies analysis, but requires some understanding of the rate of growth of some common functions.

Rate of Growth

For most practical algorithms the run times are polynomial - bounded by by some polynomial in n, the size of the problem. Here are some functions that are bounded by a polynomial. Note that nk×log(n) is bounded by nk+1 for almost every n (all but a finite number of values of n).

f(n) n = 103 (1K) n = 106 (1M) n = 109 (1G)
1 1 1 1
log(n) 10 20 30
√n 3.2×101 (32) 103 (1K) 3.2×104 (32K)
n 103 (1K) 106 (1M) 109 (1G)
n×log(n) 104 (10K) 2×107 (20M) 3×1010 (30G)
n2 106 (1M) 1012 (1T) 1018
n3 109 (1G) 1018 1027

Exhaustive search algorithms often have exponential or worse run times. Here are some functions that are exponential or worse. Note that the n values in this table are much smaller than in the table above.

f(n) n = 10 n = 20 n = 30
2n 103 (1K) 106 (1M) 109 (1G)
3n 5.9×104 (59K) 3.5×109 (3.5G) 2.1×1014
n! 3.6×106 (1M) 2.4×1018 2.7×1032

Insertion Sort

Some simple algorithms can be analyzed for run time by simply adding up the amount of time spent in each line of code. This amounts to adding up terms for each line of code. Each term has the form

run-time-for-a-single-execution × number-of-executions

This is almost always easier with "Big O" notation, which can absorb unknown constants.

code time
for j = 1 to A.length - 1 O(n)
key = A[j] O(n)
i = j O(n)
while i > 0 && A[i - 1] > key Σtj×O(1)
A[i] = A[i - 1] Σtj×O(1)
i = i - 1 Σtj×O(1)
A[i] = key O(n)

In this analysis tj is the number of steps down from index j that are needed to find the proper place for key. In the worst case tj = j. On the average it is about half that, but still O(j). The sum of the tj from j = 2 to j = n is then O(n2).

Amortized Run Times

TITLE