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 ```cpp // O(n) space — new vector of size n vector 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 }

</div>
</div>
<div class="chapter-section">
<h2 class="section-heading">Section 3 — Recursion Fundamentals</h2>
<p>Recursion is a function calling itself with a smaller, simpler version of the same problem. Every recursive function must have exactly two parts:</p>
<div class="insight-box">
  <span class="insight-label">Two Required Components</span>
  <ul>
<li><strong>Base case:</strong> The condition under which the function stops calling itself and returns a direct answer.</li>
<li><strong>Recursive case:</strong> Reduce the problem to a smaller subproblem and call yourself again.</li>
  </ul>
  Without a base case → infinite recursion → stack overflow. Without a recursive case → no recursion.
</div>
<h3 class="section-subheading">3.1 — The Call Stack</h3>
<p>Every function call occupies a frame on the call stack. Recursive calls stack up sequentially, then unwind once the base case is hit:</p>
<div class="ch-code-wrap">
<span class="ch-code-label">Fibonacci — trace the call stack</span>
```cpp
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):

```cpp unordered_map 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 ```cpp 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