From Constant to Exponential

A Scale of Complexities

Almost all common algorithms fall into a handful of classes. Here they are, from fastest to slowest:

Notation	Name	Typical Example
O(1)	constant	accessing liste[i]
O(log n)	logarithmic	binary search, balanced BST
O(n)	linear	scanning through a list
O(n log n)	quasi-linear	good sorts (merge sort, quicksort)
O(n^2)	quadratic	bubble sort, nested loops
O(2^n)	exponential	trying every combination

Visualizing Them: The Explosion of the Curves

The most telling approach is to draw how the cost grows with n. The faster the curve rises, the worse it is.

  cost
   ^
   |                                             . 2^n  (vertical wall)
   |                                          .
   |                                       .
   |                                    .        n^2
   |                                .        _.-'
   |                            . _.-''''
   |                       _.-'''         ______ n log n
   |                 _.-'''      ________/________ n
   |            _.-'''  ________/
   |       _.-'_______/                _____________ log n
   |  _.-''_______________________________________ 1
   +------------------------------------------------> n

O(1) and O(log n) stay nearly flat: they handle gigantic inputs without flinching. O(2^n) climbs so fast that it becomes an impassable wall after just a few dozen elements.

The Table That Hurts

Let's translate this into number of operations for different sizes. Assuming one operation takes one nanosecond:

     n  |  log n |     n     |  n log n  |    n^2      |         2^n
  ------+--------+-----------+-----------+-------------+---------------------
    10  |   ~3   |    10     |    ~33    |    100      |        1 024
   100  |   ~7   |   100     |   ~664    |  10 000     |   ~10^30 (!!!)
  1 000 |  ~10   |  1 000    |  ~9 966   | 1 000 000   |   unimaginable

Look at the 2^n column: for n = 100, it reaches 10^30 operations. Even at a billion operations per second, that would take far longer than the age of the universe. An exponential algorithm is unusable beyond about thirty elements.

The Fundamental Lesson

Improving the complexity class is infinitely better than optimizing details. Going from O(n^2) to O(n log n) on a million elements means going from a trillion operations to twenty million: a factor of 50 000. No constant-factor optimization ("my code runs 2x faster") can compete with a change of class.

In Summary

Algorithms fall into a few classes, from O(1) (constant, ideal) to O(2^n) (exponential, catastrophic). The gap between these classes explodes with n: an O(log n) swallows billions of elements, an O(2^n) stalls after just thirty. Changing complexity class is the most powerful performance lever there is.