Big O notation
Big O notation describes how the amount of work an operation performs grows as its input grows. It does not predict an exact number of milliseconds. Instead, it helps answer a practical question: will this approach still be affordable when there are many more reports?
Why Big O matters
An approach that checks ten reports may feel instant. If it checks every report and the collection grows to ten million reports, the same approach may become slow. Big O helps us notice that growth pattern while we are designing the program.
Big O also makes it easier to compare the case-study structures. An array can read an item by position in constant time, while an unsorted report log may need to search item by item. The same operation can have a different cost depending on how the data is organized.
Reading the notation
In O(n), n means the number of input items. The O describes the growth rate, not a precise measurement.
| Notation | How the work grows | Simple example |
|---|---|---|
O(1) | Stays about the same | Read an item at a known array index |
O(log n) | Grows slowly by reducing the search space | Search sorted data by repeatedly halving it |
O(n) | Grows with the number of items | Scan a collection from beginning to end |
O(n log n) | Combines repeated passes with halving | Efficient comparison-based sorting |
O(n²) | Each item may interact with every other item | Compare every pair of items |
O(1): constant work
The input size does not substantially change the amount of work. Accessing a known position in an array is the classic example:
scores = [10, 20, 30]
second_score = scores[1]Whether the array contains three values or three million, the program can go directly to position 1. The operation is O(1).
O(n): one pass through the data
If the program does not know where a value is, it may need to inspect items one at a time:
for each name in names:
if name equals target:
return found
return not foundIn the worst case, every one of the n names is checked. The search is O(n). Processing each of n items once is commonly O(n). A loop inside another loop may be O(n²), but the actual bounds should be examined rather than guessed from indentation alone.
O(log n): repeatedly halve the work
Binary search works on sorted data. It checks the middle item, then discards the half that cannot contain the target. Each step cuts the remaining search space in half, so the work grows as O(log n).
while the search range is not empty:
inspect the middle item
keep only the half that could contain the targetThe structure of the data matters: binary search cannot safely skip half of an unsorted collection.
O(n²): work inside work
Nested operations can cause quadratic growth:
for each left item in items:
for each right item in items:
compare left item with right itemWith 10 items, the inner operation may run about 100 times. With 1,000 items, it may run about 1,000,000 times. Nested loops are not always wrong, but their growth deserves attention.
Time and space
Big O can describe time, but it can also describe extra memory. An operation that uses a second collection containing n items has O(n) additional space. Sometimes using more memory is a worthwhile trade for faster lookup.
For example, a set may use extra memory to make membership checks fast. A linked list uses memory for links between nodes. Good design considers both the time and space costs.
Big O is a guide, not the whole decision
Big O usually describes the dominant growth as n becomes large. It often leaves out constant factors and average-case details. A hash-based dictionary may provide average O(1) lookup, but it still needs memory and can resize. A simple linear scan may be perfectly reasonable for a tiny collection.
The best question is not “Which structure has the smallest Big O?” Ask instead:
- Which help desk operation is being measured?
- How large can the ticket or relationship data become?
- Does the structure preserve the required rule, such as order or uniqueness?
- What time and extra memory can the program afford?