Logarithmic time describes an algorithm whose running time grows with the logarithm of the input size. Each additional step can handle a much larger input, so growth stays slow as lists become bigger. section 1.10 section 1.5
Folding a grid
Drawing 16 boxes one at a time takes 16 operations, or O(n). Folding paper doubles the number of boxes each time: four folds produce 16 boxes, so the same task takes O(log n) time. section 1.8
Compare logarithmic growth with familiar running times:
- Binary search uses O(log n): at most seven guesses find an item in 100 entries, and at most 32 guesses handle 4 billion entries. section 1.5
- Simple search uses O(n), checking items one by one; logarithmic time becomes increasingly faster than linear time as the input grows. section 1.12
- A balanced recursive process can have O(log n) levels, as in quicksort’s best-case call stack, although each level may add O(n) work. section 4.5
Run times for search algorithms
Use the search-runtime figure to compare logarithmic and linear growth visually. section 1.5
