Linear time describes an algorithm whose running time grows with the size of its input. If a simple search checks items one by one, a list of 100 items can require up to 100 guesses, while 4 billion items can require up to 4 billion guesses. The number of operations grows in step with the list. section 1.5
Big O notation writes linear time as O(n), where n represents the input size. This notation focuses on how operation counts grow rather than promising an exact number of seconds. section 1.10 section 1.12
Drawing a grid
Imagine drawing one box at a time. Drawing 16 boxes takes 16 steps, so the algorithm takes O(n) time. A folding method creates many boxes per operation and takes O(log n) time instead, showing why input growth matters. section 1.8
Use these comparisons to recognize linear growth:
- Simple search may inspect every item, making its maximum number of guesses equal to the list size. section 1.5
- Binary search grows logarithmically, so it becomes much faster than linear search as the list grows. section 1.12
- O(n) can also describe a worst-case call-stack size, even when the full algorithm has a different running time. section 4.5
Drawing a grid one box at a time
Compare the visual sequence of drawing a grid one box at a time with faster ways to increase the number of boxes. section 1.8
