Time Complexity
How does the amount of work grow as the input gets bigger? Let n mean the input size.
Basics
x = nums[0] # O(1)
for x in nums: # O(n)
...
for x in nums: # O(n²)
for y in nums:
...Quick rule: one lookup → O(1), one full scan → O(n), nested full scans → O(n²).
Ignore constants and smaller terms: O(2n) → O(n), O(n + 10) → O(n), O(n² + n) → O(n²).
Function calls
A function call is not automatically O(1). Include the work inside it.
nums.sort() # O(n log n)
One after another → add
helper(nums) # O(n) helper(nums) # O(n) # O(n) + O(n) = O(n)
Repeated inside a loop → multiply
for x in nums: # n times
helper(nums) # O(n) each
# n × n = O(n²)Recursion
Ask: How many calls are made, and how much work does each call do?
def countdown(n: int):
if n == 0:
return
countdown(n - 1)
# one chain of n calls → O(n)def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# branching calls → exponential timeWithout memoization, Fibonacci repeatedly solves the same smaller problems. O(2ⁿ) is a useful simple upper bound.
Dynamic programming
DP avoids recalculating the same smaller problems.
| Approach | Time |
|---|---|
| Plain branching recursion | O(2ⁿ) |
| Memoization | O(n) |
| 1D DP | O(n) |
| Rolling variables | O(n) |
Why exponential gets bad quickly
| n | O(n) | O(n²) | O(2ⁿ) |
|---|---|---|---|
| 10 | 10 | 100 | 1,024 |
| 20 | 20 | 400 | 1,048,576 |
| 50 | 50 | 2,500 | > 1 quadrillion |