Data Structures & AlgorithmsRecursion

Time & Space Complexity of Recursive Algorithms

LevelIntermediate

Duration75 mins

TopicRecursion

4 / 4

Master Theorem Intuition (Conceptual)

A Formula That Solves Recurrences Instantly

Throughout this module, we've solved recurrences by expansion and recursion trees. These methods are instructive but time-consuming. What if there were a formula—a recipe—that could give you the answer to most divide-and-conquer recurrences immediately, without any expansion at all?

The Master Theorem is exactly that. It's a closed-form solution for recurrences of the form T(n) = a·T(n/b) + f(n), covering the vast majority of divide-and-conquer algorithms you'll encounter. Once you internalize the Master Theorem, recurrence analysis becomes nearly instant.

What You Will Learn

By the end of this page, you will understand the intuition behind the Master Theorem, recognize which recurrences it applies to, and be able to apply it to instantly determine the complexity of divide-and-conquer algorithms. We focus on conceptual understanding, not just mechanical application.

The Form of Divide-and-Conquer Recurrences

The Master Theorem applies to recurrences of a specific form—the form that naturally arises from divide-and-conquer algorithms:

1
2
3
4
5
6
7
8
9
10
11
T(n) = a · T(n/b) + f(n)
 
Where:
• a ≥ 1: Number of recursive subproblems
• b > 1: Factor by which the problem size shrinks
• f(n): Cost of dividing the problem and combining solutions
• T(n/b): Time to solve each subproblem
 
The recurrence reads:
"To solve a problem of size n, we solve 'a' subproblems 
of size n/b, then do f(n) additional work."

Mapping algorithms to this form:

Divide-and-Conquer Algorithms in Standard Form
Algorithm	Recurrence	a	b	f(n)
Binary Search	T(n) = 1·T(n/2) + O(1)	1	2	Θ(1)
Merge Sort	T(n) = 2·T(n/2) + O(n)	2	2	Θ(n)
Strassen's Matrix Mult.	T(n) = 7·T(n/2) + O(n²)	7	2	Θ(n²)
Karatsuba Multiplication	T(n) = 3·T(n/2) + O(n)	3	2	Θ(n)
Quickselect (best case)	T(n) = 1·T(n/2) + O(n)	1	2	Θ(n)
Tree Traversal (balanced)	T(n) = 2·T(n/2) + O(1)	2	2	Θ(1)

When the Master Theorem Doesn't Apply

The Master Theorem doesn't apply to: (1) Recurrences with non-constant coefficients like T(n) = T(n-1) + O(n), (2) Recurrences where subproblem sizes aren't equal, like T(n) = T(n/3) + T(2n/3) + O(n), (3) Recurrences with variable number of subproblems like T(n) = n·T(n-1). These require other techniques.

The Core Intuition: Where Does the Work Go?

The Master Theorem's power comes from a simple insight: in any divide-and-conquer algorithm, the total work is dominated by one of three possibilities:

Work at the leaves (the base cases)
Work at the root (the original problem level)
Work is balanced across all levels

The Master Theorem determines which case applies by comparing the rate at which work grows/shrinks as we descend the recursion tree.

Visualizing the recursion tree:

1
2
3
4
5
6
7
8
9
10
11
12
Level 0 (root):        [     f(n)     ]              1 node
                           /   |   \
Level 1:          [f(n/b)] [f(n/b)] ...               a nodes
                    / | \    / | \
Level 2:      [f(n/b²)] ... [f(n/b²)]                 a² nodes
                    ...
Level k:           a^k nodes, each doing f(n/b^k) work
 
Total depth: log_b(n) levels
Total leaves: a^(log_b(n)) = n^(log_b(a))
 
The question: Which level dominates the total work?

The critical comparison:

The answer depends on comparing n^(log_b(a)) (number of leaves, representing work at the bottom) with f(n) (work at the top).

If leaves dominate (bottom-heavy tree): T(n) = Θ(n^(log_b(a)))
If root dominates (top-heavy tree): T(n) = Θ(f(n))
If work is balanced (uniform tree): T(n) = Θ(f(n) · log n)

The Weight Metaphor

Think of the recursion tree as a balance scale. On one side: the work at the leaves (n^log_b(a)). On the other side: the work at the root (f(n)). The Master Theorem asks: which side is heavier? The heavier side determines the complexity. If they're equal, both contribute equally and you get an extra log factor.

The Three Cases of the Master Theorem

Given T(n) = a·T(n/b) + f(n), compare f(n) with n^(log_b(a)). Let's call c_crit = log_b(a) the critical exponent.

Case 1: Leaf-Dominated (Bottom-Heavy)

1
2
3
4
5
6
7
8
9
10
11
12
13
Condition: f(n) = O(n^c) where c < log_b(a)
          (Root work grows slower than leaf count)
 
Result: T(n) = Θ(n^(log_b(a)))
 
Intuition: The leaves do most of the work. The number of leaves
          grows faster than the work per node shrinks, so work
          accumulates at the bottom.
 
Example: T(n) = 8·T(n/2) + Θ(n²)
         log_b(a) = log₂(8) = 3
         f(n) = n² = O(n^c) where c = 2 < 3
         → T(n) = Θ(n³)

Case 2: Root-Dominated (Top-Heavy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Condition: f(n) = Ω(n^c) where c > log_b(a)
          AND a·f(n/b) ≤ k·f(n) for some k < 1 (regularity condition)
          (Root work dominates leaf work)
 
Result: T(n) = Θ(f(n))
 
Intuition: The root does most of the work. The work at each level
          shrinks fast enough that lower levels become negligible.
          It's like a geometric series that converges.
 
Example: T(n) = T(n/2) + Θ(n)
         log_b(a) = log₂(1) = 0
         f(n) = n = Ω(n^c) where c = 1 > 0
         → T(n) = Θ(n)

Case 3: Balanced (Equal Weight)

1
2
3
4
5
6
7
8
9
10
11
12
13
Condition: f(n) = Θ(n^(log_b(a)))
          (Root work equals leaf count asymptotically)
 
Result: T(n) = Θ(n^(log_b(a)) · log n)
             = Θ(f(n) · log n)
 
Intuition: Every level does equal work. There are log n levels,
          each doing Θ(f(n)) work. Total = f(n) × log n.
 
Example: T(n) = 2·T(n/2) + Θ(n)  (Merge Sort!)
         log_b(a) = log₂(2) = 1
         f(n) = n = Θ(n^1)
         → T(n) = Θ(n log n)

The Regularity Condition

Case 2 has a 'regularity condition' that ensures f(n) shrinks smoothly. This is satisfied by most polynomial functions and can usually be assumed to hold. It exists to exclude pathological functions that oscillate wildly.

The Simplified Approach: Comparing Exponents

For practical use, there's a simplified way to think about the Master Theorem when f(n) is a polynomial (which it usually is):

If f(n) = Θ(n^d), compare d with log_b(a):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given: T(n) = a·T(n/b) + Θ(n^d)
 
Compute: c_crit = log_b(a)
 
Compare d with c_crit:
 
┌─────────────────┬───────────────────────────────┐
│   Comparison    │           Result              │
├─────────────────┼───────────────────────────────┤
│   d < log_b(a)  │  T(n) = Θ(n^(log_b(a)))       │
│   d = log_b(a)  │  T(n) = Θ(n^d · log n)        │
│   d > log_b(a)  │  T(n) = Θ(n^d)                │
└─────────────────┴───────────────────────────────┘
 
Memory aid:
• d smaller → leaf exponent wins
• d equal   → tie → multiply by log n
• d larger  → root exponent wins

Why log_b(a)?

The number log_b(a) represents the "rate of subproblem expansion." At each level:

We create a times more subproblems
Each subproblem is b times smaller

After log_b(n) levels, we have a^(log_b(n)) = n^(log_b(a)) leaves. This is the "natural" growth rate of the algorithm. If the per-node work f(n) keeps pace with this rate (Case 3), work is balanced. If f(n) is slower (Case 1), leaves dominate. If f(n) is faster (Case 2), the root dominates.

The log_b(a) Calculation

log_b(a) asks: 'What power of b gives a?' Examples: log₂(2) = 1, log₂(4) = 2, log₂(8) = 3, log₃(9) = 2. For non-obvious cases, use the formula: log_b(a) = ln(a)/ln(b). Or just remember common cases!

Worked Examples: Applying the Master Theorem

Let's apply the Master Theorem to important algorithms:

Example 1: Binary Search

1
2
3
4
5
6
7
8
T(n) = 1·T(n/2) + Θ(1)
 
a = 1, b = 2, f(n) = Θ(n⁰) → d = 0
log_b(a) = log₂(1) = 0
 
Compare: d = 0 = log_b(a)  →  Case 3 (equal)
 
Result: T(n) = Θ(n⁰ · log n) = Θ(log n)   ✓

Example 2: Merge Sort

1
2
3
4
5
6
7
8
T(n) = 2·T(n/2) + Θ(n)
 
a = 2, b = 2, f(n) = Θ(n¹) → d = 1
log_b(a) = log₂(2) = 1
 
Compare: d = 1 = log_b(a)  →  Case 3 (equal)
 
Result: T(n) = Θ(n¹ · log n) = Θ(n log n)   ✓

Example 3: Tree Traversal (Balanced Binary Tree)

1
2
3
4
5
6
7
8
9
10
T(n) = 2·T(n/2) + Θ(1)
 
a = 2, b = 2, f(n) = Θ(n⁰) → d = 0
log_b(a) = log₂(2) = 1
 
Compare: d = 0 < 1 = log_b(a)  →  Case 1 (leaves dominate)
 
Result: T(n) = Θ(n^(log₂(2))) = Θ(n)   ✓
 
Intuition: We visit every node once, so O(n) makes sense.

Example 4: Strassen's Matrix Multiplication

1
2
3
4
5
6
7
8
9
10
T(n) = 7·T(n/2) + Θ(n²)
 
a = 7, b = 2, f(n) = Θ(n²) → d = 2
log_b(a) = log₂(7) ≈ 2.807
 
Compare: d = 2 < 2.807 = log_b(a)  →  Case 1 (leaves dominate)
 
Result: T(n) = Θ(n^(log₂(7))) = Θ(n^2.807) ≈ Θ(n^2.81)   ✓
 
This is better than naive matrix multiplication's O(n³)!

Example 5: Quickselect (Best Case)

1
2
3
4
5
6
7
8
9
10
11
T(n) = 1·T(n/2) + Θ(n)
 
a = 1, b = 2, f(n) = Θ(n¹) → d = 1
log_b(a) = log₂(1) = 0
 
Compare: d = 1 > 0 = log_b(a)  →  Case 2 (root dominates)
 
Result: T(n) = Θ(n)   ✓
 
Even though we recurse, the first partition does O(n) work,
and subsequent work forms a geometric series: n + n/2 + n/4 + ... = O(n).

Geometric Series Connection

Case 2 (root dominates) corresponds to a geometric series where each level does significantly less work than the previous. The sum converges to O(f(n)), dominated by the first term. Case 1 (leaves dominate) is an inverse geometric series growing toward the leaves.

Common Cases to Memorize

With enough practice, you won't need to compute log_b(a) each time. Memorize these common patterns:

Common Master Theorem Results
Recurrence	a	b	f(n)	log_b(a)	Case	Result
T(n) = T(n/2) + O(1)	1	2	O(1)	0	3	O(log n)
T(n) = T(n/2) + O(n)	1	2	O(n)	0	2	O(n)
T(n) = 2T(n/2) + O(1)	2	2	O(1)	1	1	O(n)
T(n) = 2T(n/2) + O(n)	2	2	O(n)	1	3	O(n log n)
T(n) = 2T(n/2) + O(n²)	2	2	O(n²)	1	2	O(n²)
T(n) = 4T(n/2) + O(n)	4	2	O(n)	2	1	O(n²)
T(n) = 4T(n/2) + O(n²)	4	2	O(n²)	2	3	O(n² log n)
T(n) = 3T(n/2) + O(n)	3	2	O(n)	~1.58	1	O(n^1.58)

Quick reference patterns:

•T(n) = 2T(n/2) + O(n) → O(n log n) — The merge sort pattern. The most common in practice.
•T(n) = T(n/2) + O(1) → O(log n) — Binary search. Single call, halving, constant work.
•T(n) = T(n/2) + O(n) → O(n) — Linear reduction with geometric decay. Root dominates.
•T(n) = 2T(n/2) + O(1) → O(n) — Tree traversal. Leaves dominate. Visit all nodes.
•T(n) = 4T(n/2) + O(n) → O(n²) — Four subproblems, linear combine. Leaves win.

The '2T(n/2) + n' Pattern

The recurrence T(n) = 2T(n/2) + O(n) yielding O(n log n) is so common that it's worth memorizing as a single unit. When you see 'divide in half, merge linearly,' you should instantly think 'n log n.'

Beyond the Basic Master Theorem

The Master Theorem is powerful but not universal. Here's what to do when it doesn't apply:

When Subproblem Sizes Differ:

1
2
3
4
5
6
T(n) = T(n/3) + T(2n/3) + O(n)
 
The Master Theorem assumes equal subproblem sizes.
For unequal sizes, use the Akra-Bazzi theorem or recursion trees.
 
This recurrence (from randomized quicksort analysis) solves to O(n log n).

When f(n) Has Logarithmic Factors:

1
2
3
4
5
6
T(n) = 2T(n/2) + O(n log n)
 
This is between Case 2 and Case 3.
The extended Master Theorem handles such cases.
 
Result: T(n) = O(n log² n)

When Subproblems Don't Shrink by a Constant Factor:

1
2
3
4
5
6
T(n) = T(n-1) + O(n)   (NOT T(n) = T(n/b) + ...)
 
This is NOT divide-and-conquer; it's linear reduction.
The Master Theorem doesn't apply.
 
Solve by expansion: T(n) = n + (n-1) + ... + 1 = O(n²)

The Akra-Bazzi Theorem

For more complex recurrences like T(n) = T(n/3) + T(2n/3) + O(n), the Akra-Bazzi theorem provides a generalization. In advanced algorithms courses, you may encounter this more powerful tool. For most practical purposes, the basic Master Theorem suffices.

Practical Tips and Intuition

Here's practical wisdom for using the Master Theorem in the real world:

Master Theorem Intuition

•If a = b, expect O(n) — Equal branching and shrinking balances out, visiting roughly n nodes with O(1) each.
•If a < b and f(n) = O(1), expect O(log n) — Few subproblems, big shrink. Binary search territory.
•If a = b² and f(n) = O(n), expect O(n log n) — Classic divide-and-conquer. Merge sort territory.
•If a > b² and f(n) = O(n), expect O(n^something > 1) — Subproblems multiplying faster than they shrink. Leaves dominate.
•Constant work f(n) = O(1) usually leads to Case 1 — When you do O(1) per call, the number of calls dominates.
•Linear work f(n) = O(n) creates the most interesting cases — It can be any of the three cases depending on a and b.

The sanity check:

After applying the Master Theorem, sanity-check your answer:

Lower bound: You must examine every element at least once for most problems. If your answer is O(log n), make sure you're not supposed to touch all n elements (like in sorting).
Upper bound: Your answer shouldn't exceed the naive approach. Merge sort can't be worse than O(n²) comparison sort.
Intuition match: Does the answer feel right for what the algorithm does?

Don't Blindly Apply

The Master Theorem is a tool, not a substitute for understanding. Always verify: (1) The recurrence is in the right form, (2) a, b, and f(n) are correctly identified, (3) The case determination is correct. A wrong setup gives a wrong answer.

Summary: The Master Theorem

The Master Theorem provides instant solutions for divide-and-conquer recurrences. Let's consolidate what we've learned:

Key Takeaways

•The Master Theorem applies to T(n) = a·T(n/b) + f(n) — Divide-and-conquer algorithms naturally produce this form.
•Compare f(n) with n^(log_b(a)) to determine the case — This comparison determines whether leaves, root, or all levels dominate.
•Case 1 (f(n) smaller): T(n) = Θ(n^(log_b(a))) — Leaves dominate. Work accumulates at the bottom.
•Case 2 (f(n) larger): T(n) = Θ(f(n)) — Root dominates. Work geometric series converges.
•Case 3 (f(n) equal): T(n) = Θ(f(n) log n) — Balanced. Equal work per level × log n levels.
•Memorize common patterns for instant recognition — T(n) = 2T(n/2) + O(n) → O(n log n) should be automatic.
•The Master Theorem isn't universal — Recurrences with linear reduction or unequal subproblems need other methods.

Module Complete:

Congratulations! You've completed the module on Time & Space Complexity of Recursive Algorithms. You now possess the tools to:

Write recurrence relations from recursive code
Solve recurrences through expansion and recursion trees
Recognize exponential vs polynomial algorithms at a glance
Apply the Master Theorem for instant divide-and-conquer analysis
Understand stack space consumption and its limits

These skills are fundamental to algorithm design and analysis. They enable you to predict algorithm behavior, choose between approaches, and design efficient solutions from the ground up.

Module Complete

You have mastered the analysis of recursive algorithm complexity. You understand recurrence relations, can analyze space and time complexity, distinguish tractable from intractable recursion, and apply the Master Theorem. These skills form the foundation for designing and optimizing algorithms in your engineering career.

4 / 4

Loading learning content...

Data Structures & AlgorithmsRecursion

Time & Space Complexity of Recursive Algorithms

LevelIntermediate

Duration75 mins

TopicRecursion

4 / 4

Master Theorem Intuition (Conceptual)

A Formula That Solves Recurrences Instantly

What You Will Learn

The Form of Divide-and-Conquer Recurrences

The Master Theorem applies to recurrences of a specific form—the form that naturally arises from divide-and-conquer algorithms:

1
2
3
4
5
6
7
8
9
10
11
T(n) = a · T(n/b) + f(n)
 
Where:
• a ≥ 1: Number of recursive subproblems
• b > 1: Factor by which the problem size shrinks
• f(n): Cost of dividing the problem and combining solutions
• T(n/b): Time to solve each subproblem
 
The recurrence reads:
"To solve a problem of size n, we solve 'a' subproblems 
of size n/b, then do f(n) additional work."

Mapping algorithms to this form:

Divide-and-Conquer Algorithms in Standard Form
Algorithm	Recurrence	a	b	f(n)
Binary Search	T(n) = 1·T(n/2) + O(1)	1	2	Θ(1)
Merge Sort	T(n) = 2·T(n/2) + O(n)	2	2	Θ(n)
Strassen's Matrix Mult.	T(n) = 7·T(n/2) + O(n²)	7	2	Θ(n²)
Karatsuba Multiplication	T(n) = 3·T(n/2) + O(n)	3	2	Θ(n)
Quickselect (best case)	T(n) = 1·T(n/2) + O(n)	1	2	Θ(n)
Tree Traversal (balanced)	T(n) = 2·T(n/2) + O(1)	2	2	Θ(1)

When the Master Theorem Doesn't Apply

The Core Intuition: Where Does the Work Go?

The Master Theorem's power comes from a simple insight: in any divide-and-conquer algorithm, the total work is dominated by one of three possibilities:

Work at the leaves (the base cases)
Work at the root (the original problem level)
Work is balanced across all levels

The Master Theorem determines which case applies by comparing the rate at which work grows/shrinks as we descend the recursion tree.

Visualizing the recursion tree:

1
2
3
4
5
6
7
8
9
10
11
12
Level 0 (root):        [     f(n)     ]              1 node
                           /   |   \
Level 1:          [f(n/b)] [f(n/b)] ...               a nodes
                    / | \    / | \
Level 2:      [f(n/b²)] ... [f(n/b²)]                 a² nodes
                    ...
Level k:           a^k nodes, each doing f(n/b^k) work
 
Total depth: log_b(n) levels
Total leaves: a^(log_b(n)) = n^(log_b(a))
 
The question: Which level dominates the total work?

The critical comparison:

The answer depends on comparing n^(log_b(a)) (number of leaves, representing work at the bottom) with f(n) (work at the top).

If leaves dominate (bottom-heavy tree): T(n) = Θ(n^(log_b(a)))
If root dominates (top-heavy tree): T(n) = Θ(f(n))
If work is balanced (uniform tree): T(n) = Θ(f(n) · log n)

The Weight Metaphor

The Three Cases of the Master Theorem

Given T(n) = a·T(n/b) + f(n), compare f(n) with n^(log_b(a)). Let's call c_crit = log_b(a) the critical exponent.

Case 1: Leaf-Dominated (Bottom-Heavy)

1
2
3
4
5
6
7
8
9
10
11
12
13
Condition: f(n) = O(n^c) where c < log_b(a)
          (Root work grows slower than leaf count)
 
Result: T(n) = Θ(n^(log_b(a)))
 
Intuition: The leaves do most of the work. The number of leaves
          grows faster than the work per node shrinks, so work
          accumulates at the bottom.
 
Example: T(n) = 8·T(n/2) + Θ(n²)
         log_b(a) = log₂(8) = 3
         f(n) = n² = O(n^c) where c = 2 < 3
         → T(n) = Θ(n³)

Case 2: Root-Dominated (Top-Heavy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Condition: f(n) = Ω(n^c) where c > log_b(a)
          AND a·f(n/b) ≤ k·f(n) for some k < 1 (regularity condition)
          (Root work dominates leaf work)
 
Result: T(n) = Θ(f(n))
 
Intuition: The root does most of the work. The work at each level
          shrinks fast enough that lower levels become negligible.
          It's like a geometric series that converges.
 
Example: T(n) = T(n/2) + Θ(n)
         log_b(a) = log₂(1) = 0
         f(n) = n = Ω(n^c) where c = 1 > 0
         → T(n) = Θ(n)

Case 3: Balanced (Equal Weight)

1
2
3
4
5
6
7
8
9
10
11
12
13
Condition: f(n) = Θ(n^(log_b(a)))
          (Root work equals leaf count asymptotically)
 
Result: T(n) = Θ(n^(log_b(a)) · log n)
             = Θ(f(n) · log n)
 
Intuition: Every level does equal work. There are log n levels,
          each doing Θ(f(n)) work. Total = f(n) × log n.
 
Example: T(n) = 2·T(n/2) + Θ(n)  (Merge Sort!)
         log_b(a) = log₂(2) = 1
         f(n) = n = Θ(n^1)
         → T(n) = Θ(n log n)

The Regularity Condition

The Simplified Approach: Comparing Exponents

For practical use, there's a simplified way to think about the Master Theorem when f(n) is a polynomial (which it usually is):

If f(n) = Θ(n^d), compare d with log_b(a):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Given: T(n) = a·T(n/b) + Θ(n^d)
 
Compute: c_crit = log_b(a)
 
Compare d with c_crit:
 
┌─────────────────┬───────────────────────────────┐
│   Comparison    │           Result              │
├─────────────────┼───────────────────────────────┤
│   d < log_b(a)  │  T(n) = Θ(n^(log_b(a)))       │
│   d = log_b(a)  │  T(n) = Θ(n^d · log n)        │
│   d > log_b(a)  │  T(n) = Θ(n^d)                │
└─────────────────┴───────────────────────────────┘
 
Memory aid:
• d smaller → leaf exponent wins
• d equal   → tie → multiply by log n
• d larger  → root exponent wins

Why log_b(a)?

The number log_b(a) represents the "rate of subproblem expansion." At each level:

We create a times more subproblems
Each subproblem is b times smaller

The log_b(a) Calculation

Worked Examples: Applying the Master Theorem

Let's apply the Master Theorem to important algorithms:

Example 1: Binary Search

1
2
3
4
5
6
7
8
T(n) = 1·T(n/2) + Θ(1)
 
a = 1, b = 2, f(n) = Θ(n⁰) → d = 0
log_b(a) = log₂(1) = 0
 
Compare: d = 0 = log_b(a)  →  Case 3 (equal)
 
Result: T(n) = Θ(n⁰ · log n) = Θ(log n)   ✓

Example 2: Merge Sort

1
2
3
4
5
6
7
8
T(n) = 2·T(n/2) + Θ(n)
 
a = 2, b = 2, f(n) = Θ(n¹) → d = 1
log_b(a) = log₂(2) = 1
 
Compare: d = 1 = log_b(a)  →  Case 3 (equal)
 
Result: T(n) = Θ(n¹ · log n) = Θ(n log n)   ✓

Example 3: Tree Traversal (Balanced Binary Tree)

1
2
3
4
5
6
7
8
9
10
T(n) = 2·T(n/2) + Θ(1)
 
a = 2, b = 2, f(n) = Θ(n⁰) → d = 0
log_b(a) = log₂(2) = 1
 
Compare: d = 0 < 1 = log_b(a)  →  Case 1 (leaves dominate)
 
Result: T(n) = Θ(n^(log₂(2))) = Θ(n)   ✓
 
Intuition: We visit every node once, so O(n) makes sense.

Example 4: Strassen's Matrix Multiplication

1
2
3
4
5
6
7
8
9
10
T(n) = 7·T(n/2) + Θ(n²)
 
a = 7, b = 2, f(n) = Θ(n²) → d = 2
log_b(a) = log₂(7) ≈ 2.807
 
Compare: d = 2 < 2.807 = log_b(a)  →  Case 1 (leaves dominate)
 
Result: T(n) = Θ(n^(log₂(7))) = Θ(n^2.807) ≈ Θ(n^2.81)   ✓
 
This is better than naive matrix multiplication's O(n³)!

Example 5: Quickselect (Best Case)

1
2
3
4
5
6
7
8
9
10
11
T(n) = 1·T(n/2) + Θ(n)
 
a = 1, b = 2, f(n) = Θ(n¹) → d = 1
log_b(a) = log₂(1) = 0
 
Compare: d = 1 > 0 = log_b(a)  →  Case 2 (root dominates)
 
Result: T(n) = Θ(n)   ✓
 
Even though we recurse, the first partition does O(n) work,
and subsequent work forms a geometric series: n + n/2 + n/4 + ... = O(n).

Geometric Series Connection

Common Cases to Memorize

With enough practice, you won't need to compute log_b(a) each time. Memorize these common patterns:

Common Master Theorem Results
Recurrence	a	b	f(n)	log_b(a)	Case	Result
T(n) = T(n/2) + O(1)	1	2	O(1)	0	3	O(log n)
T(n) = T(n/2) + O(n)	1	2	O(n)	0	2	O(n)
T(n) = 2T(n/2) + O(1)	2	2	O(1)	1	1	O(n)
T(n) = 2T(n/2) + O(n)	2	2	O(n)	1	3	O(n log n)
T(n) = 2T(n/2) + O(n²)	2	2	O(n²)	1	2	O(n²)
T(n) = 4T(n/2) + O(n)	4	2	O(n)	2	1	O(n²)
T(n) = 4T(n/2) + O(n²)	4	2	O(n²)	2	3	O(n² log n)
T(n) = 3T(n/2) + O(n)	3	2	O(n)	~1.58	1	O(n^1.58)

Quick reference patterns:

•T(n) = 2T(n/2) + O(n) → O(n log n) — The merge sort pattern. The most common in practice.
•T(n) = T(n/2) + O(1) → O(log n) — Binary search. Single call, halving, constant work.
•T(n) = T(n/2) + O(n) → O(n) — Linear reduction with geometric decay. Root dominates.
•T(n) = 2T(n/2) + O(1) → O(n) — Tree traversal. Leaves dominate. Visit all nodes.
•T(n) = 4T(n/2) + O(n) → O(n²) — Four subproblems, linear combine. Leaves win.

The '2T(n/2) + n' Pattern

The recurrence T(n) = 2T(n/2) + O(n) yielding O(n log n) is so common that it's worth memorizing as a single unit. When you see 'divide in half, merge linearly,' you should instantly think 'n log n.'

Beyond the Basic Master Theorem

The Master Theorem is powerful but not universal. Here's what to do when it doesn't apply:

When Subproblem Sizes Differ:

1
2
3
4
5
6
T(n) = T(n/3) + T(2n/3) + O(n)
 
The Master Theorem assumes equal subproblem sizes.
For unequal sizes, use the Akra-Bazzi theorem or recursion trees.
 
This recurrence (from randomized quicksort analysis) solves to O(n log n).

When f(n) Has Logarithmic Factors:

1
2
3
4
5
6
T(n) = 2T(n/2) + O(n log n)
 
This is between Case 2 and Case 3.
The extended Master Theorem handles such cases.
 
Result: T(n) = O(n log² n)

When Subproblems Don't Shrink by a Constant Factor:

1
2
3
4
5
6
T(n) = T(n-1) + O(n)   (NOT T(n) = T(n/b) + ...)
 
This is NOT divide-and-conquer; it's linear reduction.
The Master Theorem doesn't apply.
 
Solve by expansion: T(n) = n + (n-1) + ... + 1 = O(n²)

The Akra-Bazzi Theorem

Practical Tips and Intuition

Here's practical wisdom for using the Master Theorem in the real world:

Master Theorem Intuition

•If a = b, expect O(n) — Equal branching and shrinking balances out, visiting roughly n nodes with O(1) each.
•If a < b and f(n) = O(1), expect O(log n) — Few subproblems, big shrink. Binary search territory.
•If a = b² and f(n) = O(n), expect O(n log n) — Classic divide-and-conquer. Merge sort territory.
•If a > b² and f(n) = O(n), expect O(n^something > 1) — Subproblems multiplying faster than they shrink. Leaves dominate.
•Constant work f(n) = O(1) usually leads to Case 1 — When you do O(1) per call, the number of calls dominates.
•Linear work f(n) = O(n) creates the most interesting cases — It can be any of the three cases depending on a and b.

The sanity check:

After applying the Master Theorem, sanity-check your answer:

Lower bound: You must examine every element at least once for most problems. If your answer is O(log n), make sure you're not supposed to touch all n elements (like in sorting).
Upper bound: Your answer shouldn't exceed the naive approach. Merge sort can't be worse than O(n²) comparison sort.
Intuition match: Does the answer feel right for what the algorithm does?

Don't Blindly Apply

Summary: The Master Theorem

The Master Theorem provides instant solutions for divide-and-conquer recurrences. Let's consolidate what we've learned:

Key Takeaways

•The Master Theorem applies to T(n) = a·T(n/b) + f(n) — Divide-and-conquer algorithms naturally produce this form.
•Compare f(n) with n^(log_b(a)) to determine the case — This comparison determines whether leaves, root, or all levels dominate.
•Case 1 (f(n) smaller): T(n) = Θ(n^(log_b(a))) — Leaves dominate. Work accumulates at the bottom.
•Case 2 (f(n) larger): T(n) = Θ(f(n)) — Root dominates. Work geometric series converges.
•Case 3 (f(n) equal): T(n) = Θ(f(n) log n) — Balanced. Equal work per level × log n levels.
•Memorize common patterns for instant recognition — T(n) = 2T(n/2) + O(n) → O(n log n) should be automatic.
•The Master Theorem isn't universal — Recurrences with linear reduction or unequal subproblems need other methods.

Module Complete:

Congratulations! You've completed the module on Time & Space Complexity of Recursive Algorithms. You now possess the tools to:

Write recurrence relations from recursive code
Solve recurrences through expansion and recursion trees
Recognize exponential vs polynomial algorithms at a glance
Apply the Master Theorem for instant divide-and-conquer analysis
Understand stack space consumption and its limits

These skills are fundamental to algorithm design and analysis. They enable you to predict algorithm behavior, choose between approaches, and design efficient solutions from the ground up.

Module Complete

4 / 4