1
Why Complexity Matters
Understanding Big-O before you write any code
The Core Idea: Big-O tells you how your algorithm scales as input grows. Two solutions can both be "correct" but one can be 1,000× faster on large inputs. That's why interviewers ask for time complexity.
Imagine you have a list of n names. If n = 10, any approach works fine. But if n = 1,000,000, a bad algorithm takes hours while a good one takes milliseconds. Big-O describes this difference.
| Notation | Name | Example | n = 1M → ops | Rating |
|---|---|---|---|---|
| O(1) | Constant | Array index access, HashMap get | 1 operation | ⭐⭐⭐⭐⭐ Best |
| O(log n) | Logarithmic | Binary Search | ~20 operations | ⭐⭐⭐⭐⭐ Excellent |
| O(n) | Linear | Linear Search, array loop | 1,000,000 ops | ⭐⭐⭐⭐ Good |
| O(n log n) | Linearithmic | Merge Sort, Heap Sort | ~20M operations | ⭐⭐⭐ Acceptable |
| O(n²) | Quadratic | Bubble Sort, nested loops | 1 trillion ops 🔥 | ⭐ Avoid |
| O(2ⁿ) | Exponential | Naive recursion (Fibonacci) | Larger than universe 💀 | ❌ Never |
📈 Visualizing Growth Rate (n = 8)
O(1)
1 op
O(log n)
3 ops
O(n)
8 ops
O(n log n)
24 ops
O(n²)
64 ops
Rule of Thumb for Interviews: n ≤ 10⁸ → need O(n) or better. n ≤ 10⁶ → O(n log n) is fine. n ≤ 10⁴ → O(n²) might pass. n ≤ 20 → O(2ⁿ) is okay for backtracking.
⚡
Interactive: The Complexity Race
Watch operation counts diverge as n doubles
Four algorithms race on the same input. Each step doubles n. Notice that O(log n) barely moves, and O(n²) doesn't just grow — it accelerates away. This picture is the entire reason complexity analysis exists.
📈 The same race as curves
2
The 4 Rules of Big-O
How to calculate complexity yourself
Rule 1: Drop Constants
O(2n) → O(n). Constants don't matter as n → ∞.
Rule 2: Drop Non-Dominants
O(n² + n) → O(n²). The larger term dominates.
Rule 3: Different Inputs
Two separate arrays: O(a + b), NOT O(n). Use different variables!
Rule 4: Loops Multiply
Nested loops on same array: O(n × n) = O(n²).
C++
// O(n²) — nested loops on same array
bool hasPairSum(vector<int>& arr, int target) {
for (int i = 0; i < arr.size(); i++) // O(n)
for (int j = i+1; j < arr.size(); j++) // O(n)
if (arr[i] + arr[j] == target)
return true;
return false;
}
// Total: O(n × n) = O(n²)
// Better: O(n) — use an unordered_set
bool hasPairSumFast(vector<int>& arr, int target) {
unordered_set<int> seen;
for (int num : arr) { // O(n)
if (seen.count(target - num)) // O(1)
return true;
seen.insert(num);
}
return false;
}
// Total: O(n) — 10× faster on large inputs!
3
The Problem-Solving Framework
A systematic approach to any coding problem
1
Understand the Problem (3–5 min)
Read TWICE. Ask: What's the input? What's the output? What are the constraints? Write 2–3 examples by hand. Find the edge cases (empty array, single element, negatives).
2
Brute Force First
Write the simplest solution that works, even if it's O(n²) or O(n³). This proves you understand the problem. Say the complexity out loud.
3
Optimize
Ask: What's the bottleneck? Can I preprocess? Can I use extra space (hash map) to save time? Which DS/algorithm pattern fits?
4
Code & Test
Write clean code. Use good variable names. Test with your examples. Then test edge cases: empty, single element, all duplicates, max constraints.
Common Mistake: Jumping to code before understanding the problem. You'll waste 10 minutes coding the wrong solution. Always spend 5 minutes on understanding first.
🔎
Deeper Strategy
How strong solvers actually read and attack a problem
📖 Read a Problem Statement in 4 Passes
Pass 1 — Story pass (30s): read it like a human
What is being asked, in one sentence you'd tell a friend? If you can't say it, read again — do not touch the keyboard.
Pass 2 — Contract pass: inputs, outputs, and constraints
n up to what? Values negative? Duplicates? Empty input allowed? The constraint line usually tells you the intended complexity: n ≤ 10⁵ means O(n log n) or better; n ≤ 20 whispers "bitmask or backtracking".
Pass 3 — Example pass: re-derive the sample answers by hand
If your hand-derivation disagrees with the sample output, you've misread the problem — cheapest possible time to find that out.
Pass 4 — Signal pass: hunt for trigger words
"contiguous" → window, "sorted" → two pointers / binary search, "number of ways" → DP, "all possible" → backtracking. Match phrasing to the pattern list in Phase 5.
🛠 Brute Force First — then ask the 5 Optimization Questions
Writing the brute force is never wasted: it clarifies the problem, gives you a correctness oracle, and often earns partial credit. Then interrogate it:
1. What am I recomputing?
Same subproblem twice → memoize (DP). Same window sum re-added → maintain it incrementally.
2. What am I searching linearly that has structure?
Sorted → binary search. "Have I seen this before?" → hash set. Nearest greater → monotonic stack.
3. Can I sort first without breaking the problem?
Sorting costs O(n log n) and frequently unlocks two pointers, greedy, or dedup — a great trade when order doesn't matter or indices can be carried along.
4. What information dies between iterations?
If each loop step discards knowledge the next step rebuilds (running max, prefix sum, stack of candidates), keep it alive in a variable or structure.
5. Is the answer itself searchable?
When "check if X works" is easy but "find best X" is hard, and feasibility is monotone in X — binary search on the answer.
4
14 Logic Building Drills
Practice pseudocode — no syntax required, just thinking
Each drill: read the problem, write pseudocode on paper, then reveal the solution. Do NOT look at the solution before attempting!
Drill 01
Easy
Find Max in Array
Given an array of integers, find the largest element. Constraint: no built-in max()
max_val = arr[0]
FOR each num in arr:
IF num > max_val:
max_val = num
RETURN max_val
— Time: O(n) | Space: O(1)
Drill 02
Easy
Count Even Numbers
Given an array, count how many numbers are even. Pseudocode only.
count = 0
FOR each num in arr:
IF num MOD 2 == 0:
count = count + 1
RETURN count
— Time: O(n) | Space: O(1)
Drill 03
Easy
Reverse a String
Reverse the string "hello" → "olleh". No built-in reverse functions.
left = 0, right = len(s) - 1
WHILE left < right:
SWAP s[left] and s[right]
left = left + 1
right = right - 1
RETURN s
— Time: O(n) | Space: O(1)
Drill 04
Easy
Check Palindrome
Is "racecar" a palindrome? Write the logic to check any string.
left = 0, right = len(s) - 1
WHILE left < right:
IF s[left] != s[right]:
RETURN False
left++, right--
RETURN True
— Time: O(n) | Space: O(1)
Drill 05
Easy
Sum of Digits
Given number 1234, compute 1+2+3+4 = 10. Handle any integer.
total = 0
WHILE n > 0:
digit = n MOD 10
total = total + digit
n = n / 10 (integer division)
RETURN total
— Time: O(digits) | Space: O(1)
Drill 06
Easy
Check Anagram
Are "listen" and "silent" anagrams? Two strings with same characters.
IF len(s1) != len(s2): RETURN False
freq = empty map
FOR char in s1: freq[char] += 1
FOR char in s2: freq[char] -= 1
FOR each val in freq:
IF val != 0: RETURN False
RETURN True
— Time: O(n) | Space: O(1)* 26 letters
Drill 07
Medium
FizzBuzz Classic
Print 1–100: "Fizz" if divisible by 3, "Buzz" by 5, "FizzBuzz" by both.
FOR i = 1 TO 100:
IF i MOD 15 == 0: PRINT "FizzBuzz"
ELSE IF i MOD 3 == 0: PRINT "Fizz"
ELSE IF i MOD 5 == 0: PRINT "Buzz"
ELSE: PRINT i
Note: check 15 FIRST (both conditions)
Drill 08
Medium
Find Duplicates
Given [1,2,3,2,4,3], find all numbers that appear more than once.
seen = empty set
duplicates = empty set
FOR each num in arr:
IF num in seen:
duplicates.add(num)
ELSE:
seen.add(num)
RETURN duplicates
— Time: O(n) | Space: O(n)
Drill 09
Medium
Fibonacci Sequence
Generate first n Fibonacci numbers. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).
a = 0, b = 1
FOR i = 0 TO n:
PRINT a
next = a + b
a = b
b = next
Note: iterative is O(n), recursive naive is O(2ⁿ)!
Drill 10
Medium
Binary Search
Given sorted array [1,3,5,7,9,11], find index of target=7. O(log n).
left = 0, right = len(arr) - 1
WHILE left <= right:
mid = (left + right) / 2
IF arr[mid] == target: RETURN mid
ELSE IF arr[mid] < target: left = mid + 1
ELSE: right = mid - 1
RETURN -1 (not found)
— Time: O(log n) | Space: O(1)
Drill 11
Easy
Second Largest Element
Find the second largest value in an array in one pass. Handle duplicates ([5,5,3] → 3).
first = -infinity, second = -infinity
FOR each num in arr:
IF num > first:
second = first
first = num
ELSE IF num < first AND num > second:
second = num
RETURN second
— Time: O(n) | Space: O(1)
Drill 12
Medium
Merge Two Sorted Arrays
Given two sorted arrays, produce one sorted array. This is the heart of merge sort.
i = 0, j = 0, result = []
WHILE i < len(a) AND j < len(b):
IF a[i] <= b[j]:
APPEND a[i] to result, i++
ELSE:
APPEND b[j] to result, j++
APPEND remaining of a, then remaining of b
RETURN result
— Time: O(n + m) | Space: O(n + m)
Drill 13
Medium
First Non-Repeating Character
In "swiss", the first character that appears exactly once is 'w'. Find it for any string.
counts = empty map
FOR each ch in s: // pass 1: count
counts[ch] = counts[ch] + 1
FOR each ch in s: // pass 2: first with count 1
IF counts[ch] == 1:
RETURN ch
RETURN none
— Time: O(n) | Space: O(1) (≤ 26 keys)
Drill 14
Medium
Max Sum of Any 3 Consecutive Elements
Find the largest sum over all windows of 3 consecutive elements — without re-adding each window.
window = arr[0] + arr[1] + arr[2]
best = window
FOR i from 3 to len(arr) - 1:
window = window + arr[i] - arr[i-3] // slide!
best = MAX(best, window)
RETURN best
— Time: O(n) | Space: O(1)
Naive re-adding = O(3n); sliding keeps it one op per step.
5
Complexity Quiz
Test your understanding — 5 questions
Score: 0 / 5
Q1. What is the time complexity of accessing arr[i] in an array?
Arrays store elements in contiguous memory. Index i maps directly to a memory address, so access is always O(1) regardless of array size.
Q2. You have two separate loops over array of size n. What's the total complexity?
Sequential loops ADD: O(n) + O(n) = O(2n) = O(n). Only NESTED loops multiply. Remember Rule 1: drop constants!
Q3. Which is the WORST complexity for n = 1,000,000?
O(2ⁿ) grows explosively. At n=100, it's larger than atoms in the observable universe. Always avoid exponential complexity for large inputs.
Q4. Binary search works on sorted arrays and eliminates half the search space each step. What's its complexity?
Each step cuts the search space in half. So n → n/2 → n/4 → ... → 1. That's log₂(n) steps = O(log n). For n=1M, that's only ~20 comparisons!
Q5. What's the space complexity of a recursive function that calls itself n times (like naive Fibonacci)?
Each recursive call occupies a stack frame. If the deepest recursion is n calls deep, space complexity is O(n) for the call stack — even with no extra arrays.