Big O Notation
The language of algorithm efficiency. Master how to read, write, and calculate time and space complexity.
Big O Notation
Big O notation describes how the runtime or memory usage of an algorithm scales as the input size n grows. It lets you compare algorithms without worrying about hardware, language, or constant factors.
Big O describes the upper bound — worst-case growth rate, not exact performance.
Why It Matters
Two solutions can both be "correct" but have wildly different performance at scale:
# O(n²) — works fine for n=100, painful for n=1,000,000
def has_duplicate_slow(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False
# O(n) — same result, scales to millions
def has_duplicate_fast(arr):
return len(arr) != len(set(arr))
The 8 Common Complexities
O(1) — Constant
Runtime does not depend on input size at all.
def get_first(arr):
return arr[0] # one operation regardless of len(arr)
def is_even(n):
return n % 2 == 0 # one modulo, always
def hash_lookup(d, key):
return d.get(key) # hash map lookup is O(1) average
O(log n) — Logarithmic
Input is repeatedly halved (or multiplied). Common in binary search and trees.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # cut search space in half each time
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# After k iterations, we've checked 2^k elements → k = log₂(n) iterations
O(n) — Linear
You visit every element once.
def find_max(arr):
m = arr[0]
for x in arr: # touch each element once
if x > m:
m = x
return m
O(n log n) — Linearithmic
Typical of efficient sorting algorithms — you do O(log n) levels of work, each level touching all n elements.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # log n recursive levels
right = merge_sort(arr[mid:])
return merge(left, right) # O(n) merge at each level
# Total: n elements × log n levels = O(n log n)
O(n²) — Quadratic
Two nested loops, each proportional to n.
def bubble_sort(arr):
n = len(arr)
for i in range(n): # outer: n iterations
for j in range(n - 1): # inner: ~n iterations
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
O(n³) — Cubic
Three nested loops. Quickly becomes impractical.
def matrix_multiply(A, B, n):
C = [[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n): # three nested loops
C[i][j] += A[i][k] * B[k][j]
O(2ⁿ) — Exponential
Each additional input element doubles the work. Common in naive recursion without memoization.
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2) # two recursive calls → binary tree of depth n → 2ⁿ nodes
def power_set(s):
result = [[]]
for elem in s:
result += [sub + [elem] for sub in result] # doubles each iteration → 2ⁿ subsets
return result
O(n!) — Factorial
Generating all permutations. The fastest-growing complexity — n=20 gives 2.4 quintillion operations.
def permutations(arr, start=0):
if start == len(arr) - 1:
yield arr[:]
return
for i in range(start, len(arr)):
arr[start], arr[i] = arr[i], arr[start]
yield from permutations(arr, start + 1)
arr[start], arr[i] = arr[i], arr[start]
# n choices for first, n-1 for second… = n! total permutations
Rules for Calculating Big O
Rule 1: Drop Constants
We care about growth rate, not exact multipliers.
# O(2n) → O(n)
def two_passes(arr):
for x in arr: print(x) # O(n)
for x in arr: print(x) # O(n)
# Two loops = O(2n), but we drop the 2 → O(n)
Rule 2: Drop Non-Dominant Terms
Keep only the fastest-growing term.
# O(n² + n) → O(n²)
def example(arr):
n = len(arr)
for i in range(n): # O(n)
for j in range(n): # O(n²) total
pass
for i in range(n): # O(n) — dominated, drop it
pass
| Before simplification | After | |----------------------|-------| | O(n² + n) | O(n²) | | O(2n + 100) | O(n) | | O(n + log n) | O(n) | | O(n! + 2ⁿ) | O(n!) |
Rule 3: Different Inputs = Different Variables
If two independent arrays are involved, use separate variables.
# NOT O(n²) — it's O(a * b)
def print_pairs(arr_a, arr_b):
for x in arr_a: # O(a)
for y in arr_b: # O(b)
print(x, y)
# If a == b == n then yes, O(n²). But they're independent.
Rule 4: Multi-Part Algorithms
- Sequential steps → add: O(a + b)
- Nested steps → multiply: O(a * b)
# Sequential — ADD
def add_example(arr):
sort(arr) # O(n log n)
find_max(arr) # O(n)
# Total: O(n log n + n) = O(n log n)
# Nested — MULTIPLY
def multiply_example(arr):
for x in arr: # O(n)
for y in arr: # O(n) inside
process(x, y)
# Total: O(n × n) = O(n²)
Space Complexity
Space complexity counts the extra memory your algorithm allocates, not including the input itself.
def reverse_copy(arr):
result = [] # allocates n new elements → O(n) space
for x in reversed(arr):
result.append(x)
return result
def reverse_in_place(arr):
left, right = 0, len(arr) - 1
while left < right: # only two variables → O(1) space
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
Call stack counts too! Recursive functions use O(depth) stack space.
def factorial(n):
if n <= 1: return 1
return n * factorial(n - 1)
# Stack depth = n → O(n) space even though no explicit data structure
Best, Worst, and Average Case
Big O almost always refers to the worst case in interviews, but be precise when asked:
def search(arr, target):
for i, x in enumerate(arr):
if x == target:
return i # ← could return immediately
return -1
| Case | Scenario | Complexity | |------|----------|------------| | Best | Target is first element | O(1) | | Average | Target is in the middle on average | O(n/2) = O(n) | | Worst | Target is last or not found | O(n) |
Amortized Analysis
Some operations are occasionally expensive but cheap on average. The classic example is dynamic array append:
Most appends: O(1) — just write to pre-allocated slot
Occasional: O(n) — resize (copy all elements to new array)
Amortized: O(1) — the cost averages out over many operations
Python's list.append() and Java's ArrayList.add() are both O(1) amortized.
Common Gotchas
String immutability — concatenation in a loop:
# Looks like O(n) but is actually O(n²) — each += copies the whole string
result = ""
for c in chars:
result += c
# Fix: use a list and join at the end → O(n)
result = "".join(chars)
Recursive Fibonacci without memoization:
fib(n) # O(2ⁿ) — exponential
fib_memo(n) # O(n) — with memoization
fib_dp(n) # O(n) — bottom-up DP, O(1) space if you only keep last two
Log base doesn't matter:
O(log₂ n) = O(log₁₀ n) = O(log n)
# Changing the base only changes by a constant factor, which we drop
Complexity Quick Reference
| Complexity | Name | n=10 | n=100 | n=1000 | Feasible up to | |-----------|------|-------|--------|---------|----------------| | O(1) | Constant | 1 | 1 | 1 | Any | | O(log n) | Logarithmic | 3 | 7 | 10 | Any | | O(n) | Linear | 10 | 100 | 1,000 | ~10⁸ | | O(n log n) | Linearithmic | 33 | 664 | 9,966 | ~10⁶ | | O(n²) | Quadratic | 100 | 10,000 | 10⁶ | ~10⁴ | | O(n³) | Cubic | 1,000 | 10⁶ | 10⁹ | ~500 | | O(2ⁿ) | Exponential | 1,024 | 10³⁰ | ≈∞ | ~20 | | O(n!) | Factorial | 3.6M | ≈∞ | ≈∞ | ~12 |
Interview Tips
- Always state complexity — unsolicited. "This is O(n) time, O(1) space."
- Explain the why — "O(n log n) because merge sort divides into log n levels and merges O(n) per level."
- Consider both time and space — interviewers will ask if you only give one.
- Note the trade-off — "I could get O(n) time by using O(n) extra space for a hash map."
- Simplify before speaking — O(2n + 5) → say "O(n)".
Ready to test yourself? Head to the Big O Quiz and work through 30 examples with instant feedback.