Two programs might both sort a list correctly — but one might finish in a millisecond while the other takes an hour for the same data. Time complexity gives us a way to compare algorithms mathematically, without needing to measure actual clock time. It describes how the amount of work grows as the input gets larger.
Why Input Size Matters
For small inputs, almost any algorithm is fast enough. The differences show up at scale:
| Algorithm | 10 items | 100 items | 1,000 items |
|---|---|---|---|
| O(n) | 10 ops | 100 ops | 1,000 ops |
| O(n²) | 100 ops | 10,000 ops | 1,000,000 ops |
| O(log n) | ~3 ops | ~7 ops | ~10 ops |
An algorithm that seems fine for 10 items might be completely unusable for 10,000.
Big O Notation
Big O notation describes the order of growth — how the time scales relative to the input size n. We always describe the worst case.
| Notation | Name | Example algorithm |
|---|---|---|
| O(1) | Constant | Accessing a list item by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Log-linear | Python's built-in sort (Timsort) |
| O(n²) | Quadratic | Bubble sort, selection sort |
O(1) means the algorithm always takes the same amount of time regardless of input size. Looking up my_list[5] takes the same time whether the list has 10 items or 10 million.
Counting Operations
To work out time complexity, count how many times the most important operation runs relative to n.
Example: linear search
for i in range(n):
if items[i] == target:
return i
The loop runs at most n times → O(n).
Example: bubble sort
for i in range(n):
for j in range(n - i - 1):
if items[j] > items[j + 1]:
swap...
There are two nested loops each running roughly n times → roughly n × n = n² operations → O(n²).
When you see nested loops where each loops through the full input, the time complexity is almost always O(n²). Nested loops are one of the most common causes of slow programs.
Dropping Constants and Lower Terms
In Big O notation, we ignore constants and smaller terms because they become irrelevant for large n:
5n + 100→ O(n)3n² + 7n + 50→ O(n²)2 log n + n→ O(n) (n grows faster than log n)
We only keep the dominant term — the one that grows the fastest.
Comparing Growth Rates
From fastest to slowest for large n:
O(1) < O(log n) < O(n) < O(n log n) < O(n²)
An O(log n) algorithm is dramatically faster than O(n) for large inputs. The gap between O(n) and O(n²) is even more dramatic.
Time complexity is about scaling, not raw speed. A slow O(log n) algorithm might still be faster than a fast O(n²) algorithm — but only for small inputs. At large scales, the Big O always wins.
Practice Problems
What is the time complexity of this code, and why? for i in range(n): for j in range(n): print(i, j)
Show answer
Binary search has O(log n) time complexity and linear search has O(n). For a sorted list of 1,024 items, how many comparisons does each need in the worst case?