What is Time Complexity?
Time complexity measures how the number of operations grows as input size n increases. We use Big-O notation to express the worst-case growth rate, ignoring constants and lower-order terms.
Common complexities from fastest to slowest:
O(1)
<
O(log n)
<
O(n)
<
O(n log n)
<
O(n²)
<
O(n³)
<
O(2ⁿ)
How to Count Elementary Steps
An elementary step is a single operation: assignment, comparison, arithmetic, return, or array access.
- Drop constants: O(3n) → O(n)
- Drop lower-order terms: O(n² + n) → O(n²)
- Sequential blocks: add complexities
- Nested loops: multiply complexities
- Halving/doubling loops: O(log n)
Part 1: 20 Time Complexity Problems
Simple Loops
Problem 1 — Single loop
for i in range(n):
print(i) # runs n times
// JavaScript
for (let i = 0; i < n; i++) {
console.log(i); // runs n times
}
✅ Answer: O(n) — loop runs exactly n times
Problem 2 — Loop with constant work
for i in range(n):
x = i * 2 # 1 op
y = x + 1 # 1 op
print(y) # 1 op --> 3n total
✅ Answer: O(n) — 3 operations per iteration, drop constant
Problem 3 — Loop from 0 to n/2
for i in range(n // 2):
print(i) # runs n/2 times
✅ Answer: O(n) — n/2 iterations, drop constant
Problem 4 — Two sequential loops
for i in range(n): print(i) # O(n) for j in range(n): print(j) # O(n)
✅ Answer: O(n) — O(n) + O(n) = O(2n) → O(n)
Problem 5 — Loop with step of 2
i = 0
while i < n:
print(i)
i += 2 # runs n/2 times
✅ Answer: O(n) — n/2 iterations, drop constant
Nested Loops
Problem 6 — Classic nested loop
for i in range(n):
for j in range(n):
print(i, j) # n x n = n² operations
// JavaScript
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}
✅ Answer: O(n²) — outer n × inner n
Problem 7 — Inner depends on outer
for i in range(n):
for j in range(i):
print(j) # total: 0+1+2+...+(n-1) = n(n-1)/2
✅ Answer: O(n²) — triangular sum = n(n-1)/2
Problem 8 — Inner loop is constant
for i in range(n):
for j in range(100): # always 100 iterations
print(j)
✅ Answer: O(n) — 100 × n = 100n, drop constant
Problem 9 — Triple nested loop
for i in range(n):
for j in range(n):
for k in range(n):
print(i, j, k) # n³ operations
✅ Answer: O(n³)
Problem 10 — Two different sizes
for i in range(n):
for j in range(m):
print(i, j)
✅ Answer: O(n × m) — cannot simplify unless n = m
Logarithmic Loops
Problem 11 — Doubling loop
i = 1
while i < n:
print(i)
i *= 2 # i = 1, 2, 4, 8... reaches n in log₂n steps
// JavaScript
let i = 1;
while (i < n) {
console.log(i);
i *= 2;
}
✅ Answer: O(log n) — i doubles each step
Problem 12 — Halving loop
i = n
while i > 1:
print(i)
i //= 2 # i halves each step
✅ Answer: O(log n)
Problem 13 — Linear outer, log inner
for i in range(n): # O(n)
j = 1
while j < n: # O(log n)
j *= 2
✅ Answer: O(n log n) — outer O(n) × inner O(log n)
Problem 14 — Log outer, log inner
i = 1
while i < n:
j = 1
while j < n:
j *= 2
i *= 2
✅ Answer: O(log²n) — both loops O(log n), multiplied
Mixed Patterns
Problem 15 — Sequential different complexities
for i in range(n): print(i) # O(n) i = 1 while i < n: i *= 2 # O(log n)
✅ Answer: O(n) — O(n) + O(log n) = O(n), dominant term wins
Problem 16 — Recursive factorial
def factorial(n):
if n == 0: return 1
return n * factorial(n - 1) # 1 recursive call
✅ Answer: O(n) — n recursive calls, each O(1) work
Problem 17 — Loop then nested
for i in range(n): print(i) # O(n)
for i in range(n): # O(n²)
for j in range(n): print(i,j)
✅ Answer: O(n²) — O(n) + O(n²) = O(n²), dominant term
Problem 18 — Inner halving (variable)
for i in range(n):
j = i
while j > 0:
j //= 2 # runs log(i) times for each i
✅ Answer: O(n log n) — sum of log(i) for i=1..n ≈ n log n
Part 2: 10 Space Complexity Problems
Space complexity counts auxiliary space — extra memory beyond the input itself.
Problem 1 — Constant space
def sum_array(arr):
total = 0 # 1 variable -- fixed size
for x in arr:
total += x
return total
✅ Answer: O(1) — only one extra variable regardless of n
Problem 2 — Extra output array
def double(arr):
result = [] # grows with input
for x in arr:
result.append(x * 2)
return result
✅ Answer: O(n) — result array has n elements
Problem 3 — In-place modification
def double_inplace(arr):
for i in range(len(arr)):
arr[i] *= 2 # modifies arr directly
✅ Answer: O(1) — no extra array allocated
Problem 4 — Recursive call stack
def factorial(n):
if n == 0: return 1
return n * factorial(n - 1) # n frames on stack at once
✅ Answer: O(n) — n recursive calls sit on the stack simultaneously
Problem 5 — 2D matrix allocation
def create_matrix(n):
matrix = [[0] * n for _ in range(n)] # n x n elements
return matrix
✅ Answer: O(n²) — n × n elements stored
Problem 6 — Hash map frequency count
def count_freq(arr):
freq = {}
for x in arr:
freq[x] = freq.get(x, 0) + 1 # at most n unique keys
return freq
✅ Answer: O(n) — at most n unique entries in the dict
Problem 7 — Find max
def find_max(arr):
max_val = arr[0] # 1 variable
for x in arr:
if x > max_val:
max_val = x
return max_val
✅ Answer: O(1) — only max_val regardless of n
Problem 8 — Flatten n×n matrix
def flatten(matrix): # matrix is n x n
result = []
for row in matrix:
for val in row:
result.append(val) # stores all n² elements
return result
✅ Answer: O(n²) — result stores all n × n elements
Quick Reference Table
| Complexity | Name | Example | n=1000 ops |
|---|---|---|---|
| O(1) | Constant | Array access | 1 |
| O(log n) | Logarithmic | Binary search | ~10 |
| O(n) | Linear | Linear scan | 1,000 |
| O(n log n) | Log-linear | Merge sort | ~10,000 |
| O(n²) | Quadratic | Bubble sort | 1,000,000 |
| O(2ⁿ) | Exponential | Naive Fibonacci | 10³⁰⁰ 🤯 |