Chapter 0 · Beginner · No Prerequisite

Big O Notation & Recursion

The foundation every DSA topic builds upon — learn to analyse algorithm complexity and think recursively before writing a single line of interview code.

11 Sections 4 Practice Problems Beginner ← Back to Roadmap

Section 1 — What Is Big O Notation?

Before you write a single line of code in an interview, your interviewer wants to know one thing: will your solution scale? Big O notation is the language we use to answer that question.

Big O describes how an algorithm's resource usage grows relative to its input size. It gives a worst-case upper bound on two dimensions:

Two Dimensions of Complexity

Time complexity — how many operations does the algorithm perform as input grows?
Space complexity — how much extra memory does it use? (Input itself is usually excluded)

1.1 — The Complexity Hierarchy

Memorise this table. Every time you write code, you should be able to identify which class it falls into:

Complexity	Name	Example	Acceptable for n=
O(1)	Constant	Array index access	Any
O(log n)	Logarithmic	Binary search	10⁹
O(n)	Linear	Single for-loop	10⁸
O(n log n)	Linearithmic	Merge sort, heap sort	10⁷
O(n²)	Quadratic	Nested loops	5000
O(2ⁿ)	Exponential	Subsets, backtracking	~25
O(n!)	Factorial	All permutations	~12

1.2 — Big O Rules

Drop & Simplify Rules

Drop constants: O(5n) = O(n). We care about growth rate, not the multiplier.
Drop lower-order terms: O(n² + n) = O(n²). The dominant term wins.
Different inputs = different variables: Two loops over different arrays is O(a + b), not O(n).
Nested loops multiply: An O(n) loop inside an O(m) loop = O(n × m).
Always analyse worst case unless told otherwise.

Section 2 — Analysing Common Patterns

2.1 — Loop-Based Complexity

Single Loop

O(n) — each element visited once. Default assumption for array scan.

Nested Loops

O(n²) — inner loop runs n times for each outer iteration. Two-pointer avoids this.

Half-and-Half

O(log n) — problem halved each step. Binary search, balanced BST.

Two-Phase

O(n + m) — e.g., BFS scan + preprocessing. Add, don't multiply when sequential.

2.2 — Space Complexity

Space complexity counts extra memory your algorithm allocates — not the input.
Recursive call stack counts as space: a function that recurses n times deep = O(n) space.
A HashMap storing n entries = O(n) space.
In-place operations (two-pointer reversal, bubble sort) = O(1) space.

Space complexity examples

// O(n) space — new vector of size n
vector<int> doubled(n);
for (int i = 0; i < n; i++) doubled[i] = 2 * nums[i];

// O(1) space — in-place swap
int left = 0, right = n-1;
while (left < right) swap(nums[left++], nums[right--]);

// O(n) space (call stack) — recursion depth is n
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n-1);  // n stack frames
}

Section 3 — Recursion Fundamentals

Recursion is a function calling itself with a smaller, simpler version of the same problem. Every recursive function must have exactly two parts:

Two Required Components

Base case: The condition under which the function stops calling itself and returns a direct answer.
Recursive case: Reduce the problem to a smaller subproblem and call yourself again.

Without a base case → infinite recursion → stack overflow. Without a recursive case → no recursion.

3.1 — The Call Stack

Every function call occupies a frame on the call stack. Recursive calls stack up sequentially, then unwind once the base case is hit:

Fibonacci — trace the call stack

int fib(int n) {
    if (n <= 1) return n;          // base case
    return fib(n-1) + fib(n-2);   // recursive case
}
// fib(4):
//   fib(3) → fib(2) → fib(1) → 1
//                    → fib(0) → 0
//          → fib(2) → fib(1) → 1
//                    → fib(0) → 0
//   fib(2) → fib(1) → 1
//           → fib(0) → 0
// Call tree is O(2ⁿ) without memoization!

3.2 — Memoization (Top-Down DP)

Memoization eliminates repeated subproblem computation by caching results. Transforms Fibonacci from O(2ⁿ) to O(n):

unordered_map<int,int> memo;
int fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];   // cache hit
    return memo[n] = fib(n-1) + fib(n-2); // cache result
}
// Time: O(n) — each state computed once
// Space: O(n) — memo table + call stack

Section 4 — Recursive Patterns

Linear Recursion

One recursive call per invocation. O(n) time, O(n) space (stack). Example: factorial, array sum.

Binary Recursion

Two recursive calls. O(2ⁿ) without memo. O(n) with memoization. Example: Fibonacci, merge sort.

Tree/DFS Recursion

Recurse on left and right children. O(n) for balanced tree, O(n) stack space.

Backtracking

Choose → Recurse → Unchoose. Explores O(n!) or O(2ⁿ) paths but prunes early.

Universal recursion template

ReturnType solve(params, state) {
    // 1. Base case
    if (baseCondition) return baseValue;
    // 2. Reduce problem
    subResult = solve(smallerParams, updatedState);
    // 3. Combine and return
    return combine(subResult, currentElement);
}

Practice Problems

#	Problem	Pattern	Difficulty
1	509. Fibonacci Number	Basic Recursion / Memo	Easy
2	70. Climbing Stairs	1D Memoized DP	Easy
3	231. Power of Two	Bit manipulation + recursion	Easy
4	206. Reverse Linked List	Linear Recursion	Easy