Big O Notation Explained: Algorithm Complexity Guide
Big O notation describes how an algorithm's runtime or memory grows as input size increases. It's the foundation of performance analysis: Big O tells you whether a solution will scale to 1 million items or collapse at 10,000. Understanding Big O is essential for choosing between algorithms, predicting bottlenecks before they happen, and communicating performance characteristics with teammates.
What Is Big O Notation?
Big O measures the worst-case number of operations an algorithm performs as a function of input size n. It ignores constant factors and lower-order terms, focusing only on the dominant factor. For example, an algorithm that does 3n² + 5n + 2 operations has complexity O(n²) because the n² term dominates as n grows large.
Big O answers: "If I double the input size, how many times longer will this take?" A linear O(n) algorithm takes twice as long. An O(n²) algorithm takes four times as long. An O(log n) algorithm takes slightly longer. This predictability is powerful.
The Big O Hierarchy
Here's the complexity spectrum from fastest to slowest:
| Complexity | Name | Growth | Example |
|---|---|---|---|
| O(1) | Constant | Flat line | Dictionary lookup by key |
| O(log n) | Logarithmic | Slow rise | Binary search |
| O(n) | Linear | Straight climb | Simple loop over list |
| O(n log n) | Linearithmic | Moderate rise | Efficient sorting (merge sort) |
| O(n²) | Quadratic | Steep curve | Nested loops |
| O(2ⁿ) | Exponential | Vertical cliff | Recursive fibonacci |
| O(n!) | Factorial | Nearly vertical | All permutations |
As input size doubles, O(1) stays the same, O(log n) increases slightly, O(n) doubles, O(n²) quadruples, and O(2ⁿ) explodes.
Analyzing O(1) — Constant Time
A constant-time operation takes the same number of steps regardless of input size. Dictionary and set lookups are O(1) on average:
# O(1) — always one operation
def get_user_by_id(user_dict, user_id):
return user_dict[user_id]
# Equally O(1)
def check_membership(my_set, value):
return value in my_set
Even if your dictionary has 1 item or 1 million items, a lookup is still one hash table operation. Python's dictionary implementation uses hashing, which maps keys to buckets in near-constant average time.
Analyzing O(n) — Linear Time
An O(n) algorithm's time grows proportionally with input. Simple loops are O(n):
# O(n) — loop runs n times
def find_max(numbers):
max_val = numbers[0]
for num in numbers[1:]:
if num > max_val:
max_val = num
return max_val
If numbers has 1,000 items, you do roughly 1,000 comparisons. If it has 1 million, you do 1 million. Doubling input doubles the work.
Linear is not always slow
O(n) is actually desirable because it scales predictably. You must examine the input at least once, so O(n) is optimal for problems like "find the sum" or "check if value exists."
Analyzing O(log n) — Logarithmic Time
O(log n) grows very slowly. Binary search is a classic example:
# O(log n) — divide and conquer
def binary_search(sorted_list, target):
left, right = 0, len(sorted_list) - 1
while left <= right:
mid = (left + right) // 2
if sorted_list[mid] == target:
return mid
elif sorted_list[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Each iteration eliminates half the remaining elements. For 1 million items, binary search needs at most log₂(1000000) ≈ 20 iterations. For 1 billion items, about 30 iterations. This is why binary search is practical even for enormous sorted datasets.
Analyzing O(n²) — Quadratic Time
Nested loops produce O(n²) complexity. Bubble sort and naive string matching are classic examples:
# O(n²) — nested loops
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
With n=100, you perform roughly 10,000 comparisons. With n=1,000, you perform 1 million. This rapid growth makes O(n²) impractical for large inputs. On a modern machine, O(n²) algorithms typically hit performance walls around n=100,000.
Analyzing O(n log n) — Linearithmic Time
O(n log n) falls between O(n) and O(n²). Most efficient general-purpose sorting algorithms (merge sort, quicksort) are O(n log n):
# O(n log n) — divide, sort, merge
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
O(n log n) is why Python's sorted() (which uses Timsort, a hybrid merge sort) handles 1 million items easily. For n=1 million, you perform roughly 20 million operations—manageable.
Analyzing O(2ⁿ) — Exponential Time
Exponential algorithms double in work with each additional input item. Naive recursive fibonacci is O(2ⁿ):
# O(2ⁿ) — avoid for anything larger than n=30
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# fibonacci(40) would take hours
For n=40, this function calls itself over a billion times, each call doing redundant work. O(2ⁿ) is impractical for n > 40 on modern hardware. This is why memoization (caching results) is critical for recursive algorithms.
Comparing Common Operations
Python's built-in operations have well-understood Big O complexities:
| Operation | Complexity | Notes |
|---|---|---|
| List append | O(1) amortized | Occasional resize is amortized |
| List insert (middle) | O(n) | Requires shifting elements |
| List remove (by value) | O(n) | Must search and shift |
| Set add/remove | O(1) average | Hash table insertion |
| Dict lookup/insert | O(1) average | Hash table access |
| List sort | O(n log n) | Timsort algorithm |
| Binary search | O(log n) | Input must be sorted |
| String concatenation | O(n + m) | For strings of length n, m |
Space Complexity
Big O also applies to memory. An algorithm's space complexity describes how much extra memory it uses relative to input size:
# O(n) space — creates a new list
def get_squares(numbers):
return [x**2 for x in numbers]
# O(1) space — modifies in place
def sort_in_place(arr):
arr.sort() # modifies arr, no extra space needed
return arr
The first uses extra memory proportional to input size. The second reuses the input array, requiring constant extra space. For large datasets (gigabytes), this difference matters.
Amortized Complexity
Some operations have different average and worst-case complexity. Appending to a Python list is O(1) amortized but O(n) in the worst case (when the list capacity is exceeded and must be resized). Over many appends, the average is O(1) because resizing happens infrequently.
Key Takeaways
- Big O measures how runtime grows with input size; use it to predict scalability
- O(1) is constant, O(log n) is very slow growth, O(n) is linear, O(n²) is quadratic, O(2ⁿ) is exponential
- Algorithms with O(n²) or worse typically fail on modern datasets above 10,000–100,000 items
- Choose data structures based on your primary operation: dict/set for lookups (O(1)), list for iteration (O(n))
- Space complexity matters equally; an O(1) space algorithm saves memory even if time is unchanged
Frequently Asked Questions
Is O(1) always faster than O(n)?
Not in absolute terms. A well-optimized O(n) algorithm might be faster than a poorly written O(1) with high constant factors. But Big O predicts relative growth: O(1) is always faster for very large inputs. Compare implementations of the same algorithm for fair benchmarks.
How do I know if my algorithm is O(n) or O(n log n)?
Count loops: a single loop over all input is O(n). A loop that halves the problem each iteration (like binary search) is O(log n). Two nested loops are O(n²). Use the master theorem for recursive algorithms or trace through your code manually.
Can I have O(n) space with O(log n) time?
Yes. Many algorithms trade space for time. Memoization stores results in O(n) space to achieve O(n) time for recursive algorithms. Choosing the trade-off depends on your constraints.
Does Python's Big O match other languages?
Yes. Big O is language-agnostic and describes the algorithm, not the implementation. Dictionary lookup is O(1) in Python, Java, and C++ (all use hash tables). The constant factors differ, but the growth rate is identical.
How does sorting complexity affect real applications?
Sorting is ubiquitous. Python's sorted() is O(n log n), so sorting 1 million items takes roughly 20 million operations—fractions of a second. But if you sort inside a loop (O(n²) algorithm), handling 10,000 items suddenly requires billions of operations. Always sort outside loops when possible.