How Time and Space Grows as Time Increases

How time and space grow as the amount of data increases

It's useful to estimate the cpu or memory resources an algorithm requires. This "complexity analysis" attempts to characterize the relationship between the number of data elements and resource usage (time or space) with a simple formula approximation. Many programmers have had ugly surprises when they moved from small test data to large data sets. This analysis will make you aware of potential problems.

Dominant Term

Big-Oh (the "O" stands for "order of") notation is concerned with what happens for very large values of N, therefore only the largest term in a polynomial is needed. All smaller terms are dropped.

For example, the number of operations in some sorts is N2 - N. For large values of N, the single N term is insignificant compared to N2, therefore one of these sorts would be described as an O(N2) algorithm.

Similarly, constant multipliers are ignored. So a O(4*N) algorithm is equivalent to O(N), which is how it should be written. Ultimately you want to pay attention to these multipliers in determining the performance, but for the first round of analysis using Big-Oh, you simply ignore constant factors.

Why Size Matters

Here is a table of typical cases, showing how many "operations" would be performed for various values of N. Logarithms to base 2 (as used here) are proportional to logarithms in other base, so this doesn't affect the big-oh formula.

  | constant | logarithmic | linear |   | quadratic | cubic |

n | O(1) | O(log N) | O(N) | O(N log N) | O(N2) | O(N3) |

1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 | 1 | 2 | 2 | 4 | 8 |

4 | 1 | 2 | 4 | 8 | 16 | 64 |

8 | 1 | 3 | 8 | 24 | 64 | 512 |

16 | 1 | 4 | 16 | 64 | 256 | 4,096 |

1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |

1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 | 1016 |

Does anyone really have that much data?

It's quite common. For example, it's hard to find a digital camera that that has fewer than a...