Time complexity analysis is a foundational skill for any programmer or computer science student, enabling you to predict how an algorithm's runtime scales with input size. Mastering this skill requires deliberate practice across a spectrum of problems—from simple loops to intricate recursive patterns.
Why Practice Time Complexity?
Understanding Big O notation theoretically is one thing; applying it fluently to unfamiliar code is another. Practice helps you:
- Recognize common patterns instantly (e.g., nested loops = O(n²), halving = O(log n))
- Avoid common pitfalls like miscounting triangular iterations or forgetting to drop constants
- Build intuition for recursive algorithms and amortized analysis
- Prepare confidently for technical interviews and exams
Core Concepts Recap
Before diving into problems, ensure you're comfortable with these rules:
- Drop constants: O(3n) = O(n), O(n²/2) = O(n²)
- Keep the dominant term: O(n² + n) = O(n²)
- Sequential blocks add: O(n) + O(n) = O(n)
- Nested blocks multiply: O(n) × O(n) = O(n²)
- Halving/doubling loops: O(log n)
- Graph algorithms: Typically O(V + E), where V = vertices, E = edges
Practice Problems by Difficulty
Beginner Problems (Single Loops & Constants)
Problem 1: Constant-Time Loop
What is the time complexity?
for i in range(1, 101):
print(i)
Answer: O(1) — the loop runs a fixed 100 times, independent of input size.
Problem 2: Linear Scan
for i in range(n):
print(array[i])Answer: O(n) — one iteration per element.
Problem 3: Two Sequential Loops
for x in array:
print(x)
for x in array:
print(x * 2)Answer: O(n) — sequential loops add: O(n) + O(n) = O(2n) = O(n).
Problem 4: Loop with Step
for i in range(1, n, 2):
print(i)Answer: O(n) — still linear; the step size (2) is a constant factor that gets dropped.
Intermediate Problems (Nested Loops & Logarithms)
Problem 5: Full Nested Loops
for i in range(n):
for j in range(n):
print(i, j)Answer: O(n²) — n × n iterations.
Problem 6: Triangular Nested Loops
for i in range(n):
for j in range(i + 1, n):
print(i, j)Answer: O(n²) — total iterations = n(n-1)/2, but constants are dropped.
Problem 7: Logarithmic Loop
i = n
while i > 0:
i = i // 2
print(i)Answer: O(log n) — the variable halves each iteration.
Problem 8: Linear × Logarithmic
for i in range(n):
j = 1
while j < n:
j *= 2Answer: O(n log n) — outer loop runs n times, inner loop log n times.
Problem 9: Different Input Sizes
for x in array_a: # length m
for y in array_b: # length n
print(x, y)Answer: O(m × n) — use separate variables for distinct input sizes.
Advanced Problems (Recursion & Complex Patterns)
Problem 10: Naive Fibonacci
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Answer: O(2ⁿ) — each call branches into two more calls; recursion tree depth ≈ n.
Problem 11: Memoized Fibonacci
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]Answer: O(n) — each unique subproblem (0 to n) is solved once.
Problem 12: Merge Sort
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) # O(n)Answer: O(n log n) — recurrence T(n) = 2T(n/2) + O(n).
Problem 13: Tower of Hanoi
def hanoi(n, source, target, aux):
if n == 1:
move(source, target)
return
hanoi(n-1, source, aux, target)
move(source, target)
hanoi(n-1, aux, target, source)Answer: O(2ⁿ) — recurrence T(n) = 2T(n-1) + 1.
Problem 14: All Subsets (Power Set)
def subsets(arr, i=0, current=[]):
if i == len(arr):
print(current)
return
subsets(arr, i+1, current + [arr[i]]) # include
subsets(arr, i+1, current) # excludeAnswer: O(n × 2ⁿ) — 2ⁿ subsets, each taking O(n) to copy/print.
Problem 15: BFS on a Graph
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Answer: O(V + E) — each vertex and edge is processed at most once.
Quick Reference Table
| Pattern | Complexity | Example |
|---|---|---|
| Single loop over n | O(n) | Linear search |
| nested loops over n | O(n²) | Bubble sort |
| Triple nested loops | O(n³) | Naive matrix multiply |
| Loop halving/doubling | O(log n) | Binary search |
| Loop + inner halving | O(n log n) | Merge sort, heap sort |
| Recursive, halves input | O(log n) | Binary search (recursive) |
| Recursive, two calls on n/2 + O(n) | O(n log n) | Merge sort |
| Recursive, two calls on n-1 | O(2ⁿ) | Naive Fibonacci, Hanoi |
| Memoized recursion | O(unique states) | DP Fibonacci |
| All subsets | O(n × 2ⁿ) | Power set |
| All permutations | O(n × n!) | Permutation generation |
| Graph BFS/DFS | O(V + E) | Traversal |
How to Practice Effectively
- Start simple: Master single and nested loops before tackling recursion.
- Trace small inputs: Manually count iterations for n = 3 or 4 to build intuition.
- Identify the pattern: Ask: Is it sequential or nested? Does the variable halve? Are there recursive calls?
- Write the recurrence (for recursion): Express T(n) in terms of smaller subproblems, then solve using a recursion tree or Master Theorem.
- Check edge cases: What if input sizes differ (m vs. n)? What if a loop runs a constant number of times?
Common Mistakes to Avoid
- Forgetting to drop constants: O(n²/2) is still O(n²).
- Miscounting triangular loops: j starting at i+1 still yields O(n²).
- Assuming all recursion is exponential: Halving the input (like in merge sort) gives O(n log n), not O(2ⁿ).
- Ignoring different input sizes: Nested loops over arrays of length m and n give O(mn), not O(n²).
- Overlooking amortized analysis: Some loops with inner while-loops are still O(n) if each element is processed a bounded number of times.
Next Steps
Once comfortable with these problems, challenge yourself with:
- Space complexity analysis: How much extra memory does the algorithm use?
- Best, average, and worst-case analysis: When does an algorithm perform optimally or poorly?
- Amortized analysis: Understand why some seemingly expensive operations average out to O(1).
- Master Theorem: A powerful tool for solving recurrences of the form T(n) = aT(n/b) + f(n).
Practice consistently, and soon you'll be able to glance at any code snippet and instantly determine its time complexity.
