Recurrences

21 min readOct 6, 2025

A recurrence relation expresses the running time (or value of a sequence) in terms of smaller inputs.
It’s like saying: “To solve a problem of size n, I first solve one or more smaller problems, then combine their results.”

General Form: T(n) = aT(n/b) + f(n)
where:
- T(n) = time to solve a problem of size n
- a = number of subproblems
- n/b = size of each subproblem
- f(n) = cost of dividing the problem and combining the results
Example: Merge Sort: T(n) = 2T(n/2) + cn
- Divides into 2 subproblems
- Each of size n/2
- Takes cn time to merge

When we solve a recurrence relation, we find a closed-form solution. We get an explicit formula that expresses T(n) directly in terms of n without recursion. Solving the recurrence relation means finding the asymptotic growth rate of the function. This helps us understand the time/space complexity of an algorithm.

Geometric sum

Where,

a: The first term
r: The common ratio
n: The number of terms

This single formula works whether the ratio is greater than 1, less than 1, positive, or negative, as long as it’s not exactly 1.

Infinite series (convergence / divergence)

Take the finite sum a(1−rⁿ)/(1−r).
If |r| < 1, then rⁿ → 0 as n → ∞, giving a/(1−r).
If |r| ≥ 1, the tail does not vanish, so the infinite sum does not converge.

Methods to Solve Recurrence Relations

Substitution Method (Guess & Prove)
Recursion Tree Method (Visual Approach)
Master Theorem

Substitution Method (Guess & Prove)

The substitution method is like a formal proof by induction. It involves two main steps:

Guess the Solution: the closed-form solution (e.g., O(nlog⁡n)), often by intuition or using a recursion tree.
Verify by Induction
- Show it holds for the base case.
- Assume it holds for smaller inputs (k<n) and prove it holds for n.

Useful for proving the correctness of a proposed bound, but requires a good initial guess.

Example 1: A Simple Linear Recurrence:
T(n) = T(n−1) + c, where c is a constant and T(1) = c.

Recurrence: T(n) = T(n−1) + c, where c is a constant and T(1) = c.
This recurrence describes an algorithm that does a constant amount of work 
and then reduces the problem size by one, like a simple loop.

1. Guess the Solution
By looking at the recurrence, we can see that:
    - T(1) = c
    - T(2) = T(1) + c = 2c
    - T(3) = T(2) + c = 3c
The pattern suggests that T(n) = cn. Our guess is T(n) = O(n).2. Verify with Induction
We need to prove that T(n) ≤ dn for some constant d>0.
Inductive Hypothesis: Assume the statement is true for n−1. 
That is, assume T(n−1) ≤ d(n−1).
Substitution: Now, substitute this hypothesis into the original recurrence:
    T(n) = T(n−1) + c
    T(n) ≤ d(n−1) + c
    T(n) ≤ dn − d + c
Goal: We want to show that T(n)≤dn. For our proof to work, 
we need to show that the expression we derived is less than or equal 
to our goal: dn − d + c ≤ dn
This inequality holds if (−d + c ≤ 0), which simplifies to c ≤ d.So, as long as we choose a constant d≥c, our proof is valid. 
The base case T(1) = c ≤ d(1) also holds under this condition. 
Therefore, we have proven that T(n) = O(n)

Example 2: The Merge Sort Recurrence
T(n) = 2T(n/2) + n (For simplicity, we’ll use n instead of cn).

1. Guess the Solution
From the recursion-tree method, we have a strong suspicion that the 
solution is Θ(nlogn). So, our guess is T(n) = O(nlogn).

2. Verify with Induction
We need to prove that T(n) ≤ dnlogn for some constant d>0.
Inductive Hypothesis: Assume the statement is true for smaller inputs, 
specifically for n/2.
    T(n/2) ≤ d(n/2)log(n/2)
Substitution: Substitute this into the recurrence:
    T(n) = 2T(n/2) + n
    T(n) ≤ 2(d(n/2)log(n/2)) + n
    T(n) ≤ dnlog(n/2) + n
Now, use the logarithm rule log(a/b) = loga − logb:
    T(n) ≤ dn(logn − log2) + n
Assuming we are using base-2 logarithms, log₂2 = 1:
    T(n) ≤ dn(logn − 1) + n
    T(n) ≤ dnlogn − dn + n
Goal: We want this to be ≤ dnlogn.
    dnlogn − dn + n ≤ dnlognThis inequality holds if −dn + n ≤ 0, which simplifies to n ≤ dn, or 1 ≤ d.As long as we choose a constant d ≥ 1, our proof holds for the recursive step. 
We must also check the base cases (e.g., T(2), T(3)), as the induction might 
not hold for small values of n. By choosing a large enough d, we can make 
the bound hold for these base cases as well. Thus, we have proven that T(n)=O(nlogn)

Common Pitfall in the Substitution Method

Example Recurrence: T(n) = 2T(n/2) + n
Incorrect Attempt:
    - Guess: T(n) = O(n)
    - Goal: Show T(n) ≤ cn for some constant c > 0
    - Inductive Step: Assume T(n/2) ≤ c n/2
        And substiture this into the recurrence:
        T(n) ≤ 2(cn/2) + n
        T(n) ≤ cn + n

Where It Fails:
  - Final inequality: T(n) ≤ cn + n
  - Required inequality: T(n) ≤ cn
  - However, cn + n is not less than or equal to cn (since n is positive)Conclusion:
  - The guess T(n) = O(n) is too weak
  - Actual grown is O(nlogn), that is Merge Sort
  - This illustrates a pitfall of substitution: a wrong guess leads 
    to a failed proof.

Changing Variables
- Used when a recurrence does not fit standard patterns (e.g., Master Theorem)
- Transforms the problem into a simpler form by redefining the variable.

The recurrence realation: T(n) = 2T(√n) + lg n
This is hard to solve directly because of the square root term, T(√n).
It doesn't match the T(n/b) form required by the Master Theorem.

To get rid of the square root term, √n, we introduce a new variable m.
  - Let m = lgn. This is the key substitution.
  - Rewrite n in terms of m. 
    If m = lgn, then by the definition of logarithms, n = 2ᵐ
  - Substitute into the recurrence. Replace every instance of n in 
    the original equation with its equivalent in terms of m:
        - T(n) becomes T(2ᵐ)
        - lgn becomes m
        - T(√n) becomes T(√2ᵐ) = T((2ᵐ)¹⁄²) = T(2ᵐ⁄²)
  This transforms the recurrence into:
        T(2ᵐ) = 2T(2ᵐ⁄²) + mSolving the New, Simpler Recurrence:
The equation T(2ᵐ) = 2T(2ᵐ⁄²) + m looks messy. To clean it up, we define
a new function, S(m) = T(2ᵐ)
If S(m) = T(2ᵐ), then s(m/2) = T(2ᵐ⁄²)
By substituting S into our transformed equation, we get:
    S(m) = 2S(m/2) + m
This is the exact same recurrence relation as Merge Sort, 
just with the variable m instead of n. 
We know the solution to this is: S(m) = O(mlgm)Reverting Back to the Original Variable
We've solved for S(m), but we need the solution for T(n). 
To do this, we just substitute back.
1. We found that T(n) (which is S(m)) is O(mlgm).
2. We know that our original substitution was m=lgn.Now, replace m with lgn in the solution:
  T(n) = O((lgn)lg(lgn))

Recursion Tree Method (Visual Approach)

The recursion-tree method provides an intuitive way to understand the total work an algorithm performs.
The process involves three main steps:

Build the Tree: Each node in the tree represents the cost of a single subproblem. The root is the cost of the initial call, and its children are the costs of the subsequent recursive calls.
Calculate Level Costs: The costs of all nodes at the same depth are summed up to find the cost for that entire level.
Sum Total Cost: The costs of all levels are added together to determine the total cost, which gives the overall time complexity of the algorithm.

This method is especially effective for analyzing divide-and-conquer algorithms, as their structure of breaking problems into smaller pieces maps directly onto a tree. It can be used to guess a solution (for substitution) or serve as a direct proof if analyzed rigorously.

Practical Application Notes

A common challenge in analyzing recurrences is that inputs don’t always divide perfectly (e.g., what is T(7/2)?). The recursion-tree method handles this with a two-step approach.

Assume a “Perfect” Input: The analysis often begins by assuming the input size n is an exact power of a number (e.g., for a recurrence with T(n/2), one would assume n=2ᵏ for some integer k). This simplification avoids the need for floors and ceilings, making the math much cleaner. The result obtained from this is a conditional analysis, as it’s only proven for these specific values of n.
Generalize the Result: The smoothness rule is then used to extend this conditional result to all integers. This rule applies to most functions found in algorithm analysis (specifically, functions that are non-decreasing and “polynomially bounded”). It states that if a time complexity bound holds for exact powers, it also holds for all values of n. This allows a clean, simplified proof to be applied to the general case.

Example: T(n) = T(n/3) + T(2n/3) + O(n)

The recurrence creates an unbalanced tree because the subproblems reduce the input size at different rates (one divides by 3, the other by 3/2). The input size decreases much faster along the path of the first subproblem(n/3), so the tree will be much shorter.

The height of a tree is defined by its longest path. In this case, the longest path is the one that reduces the problem size the slowest. That corresponds to the second subproblem, which only shrinks the size by a factor of 3/2 at each step.

Therefore, the height (h) is found by figuring out how many times we must divide n by 3/2 until the problem size becomes 1. This path determines the total number of generations, giving a height of h = log₍₃/₂₎ n, which is Θ(logn).

For a recurrence where the problem size is divided by b at each step, the path length (tree height) is: k = logᵦ n
Derivation: After k steps: n / bᵏ = 1 ⟹ n = bᵏ ⟹ k = logᵦ n
Example: T(n) = T(n/3) + T(2n/3) + O(n)
- Left path: divided by 3 → b = 3, length = log₃ n
- Right path: multiplied by 2/3 → same as dividing by 3/2 → b = 3/2, length = log₍₃/₂₎ n
- Tree height = longest path = log₍₃/₂₎ n
Note
- Applies to divide-and-conquer recurrences (multiplicative reduction).
- Not valid for subtractive forms (e.g., T(n) = T(n−1) + …), where height = n.

Since the cost per level is the same c·n, the next step is to determine the height of the recursion tree. When the cost is the same for each level, the total cost is (Cost per Level) × (Height of the tree)

The height of the longest path in the tree is log₍₃/₂₎ n.
Since the right subtree extends further, some levels have slightly less total work (as the left side contributes less).
However, for asymptotic analysis, such variations are negligible.
Therefore, the level cost can be approximated as c·n for all levels.

Now, the total cost is
Total Cost = (Cost per Level) × (Height of the tree)
Total Cost = (cn) × (log₍₃/₂₎ n)
Hence, the runtime is O(log₍₃/₂₎ n )

Example: T(n) = 3T(n/4) + `Θ`(n²)

Recursion Tree Analysis

Level 0: 1 node (3⁰) → cost = c·n²
Level 1: 3 nodes (3¹), each (n/4)² → total = (3/16)c·n²
Level 2: 9 nodes (3²) → total = (3/16)²c·n²
Pattern: Level i (3ⁱ) cost = (3/16)ⁱ c·n², where i is the height of the tree

Height of the Tree
The height of the recursion tree is n / 4ʰ = 1 ⟹ h = log₄ n .

Cost of the Leaves
The number of leaves is the number of nodes at the last level, which is 3ʰ .i.e,3ˡᵒᵍ₄ⁿ. Using the logarithm identity a⁽ˡᵒᵍᵦ c⁾ = c⁽ˡᵒᵍᵦ a⁾, this becomes n⁽ˡᵒᵍ₄ 3⁾. Since each leaf has a constant cost T(1), the total cost of the leaves is Θ(n⁽ˡᵒᵍ₄ 3⁾) . Since this is a precise calculation and not just an upper bound, we can say the cost is tightly bounded by n⁽ˡᵒᵍ₄ 3⁾. The correct notation for a tight bound is Big-Theta (Θ).

In this case, the level cost varies across levels, so the total cost cannot be obtained by simply multiplying the cost per level by the height.
Instead, the total cost is found by summing the costs of all levels in the tree.

The total cost is the sum of the costs of all levels plus the cost of the leaves.
T(n) = [cn² + 3.cn²/16 + 9.cn²/16² + 27.cn²/16³ + … + (3/16)^(log₄n − 1)·cn²] + Θ(n⁽ˡᵒᵍ₄ 3⁾)

The exponent log₄n − 1 represents the index of the last recursive level before reaching the leaves. Since the total height of the recursion tree is h = log₄n, levels are numbered from 0 to h. The leaves occur at level h, so the recursive work ends one level before that, at h − 1 = log₄n − 1. Thus, the summation for recursive costs stops at log₄n − 1.

We can factor out c·n² to see the structure more clearly

The series ratio r = 3/16 < 1 → Since the ratio is less than 1, the sum decreases at each step and converges to a constant. This means the cost is root-heavy; most of the work is done at the top of the tree.

Although the series is finite, when **r<1**, the infinite geometric sum gives a good approximation (and upper bound) because the remaining terms become negligible as n increases. Here, a is the first term of the series, and r is the common ratio.

Hence, the total cost for the recursive levels is therefore bounded by a constant multiple of the root’s cost: c.n²[16/13], which is O(n²).

T(n) = c.n²[16/13] + Θ(n⁽ˡᵒᵍ₄ 3⁾) T(n) = O(n²) + Θ(n⁽ˡᵒᵍ₄ 3⁾)

The recursive work is O(n²), and the leaf work is Θ(n⁽ˡᵒᵍ₄ 3⁾) .
Since log₄ 3 ≈ 0.79, this is Θ(n⁰.⁷⁹)
Clearly, the n² term grows much faster than the n⁰.⁷⁹ term. Therefore, the cost of the root dominates the entire recurrence.
Hence, the final solution is T(n) = Θ(n²).

Example: T(n) = T(n/5) + T(7n/10) + `Θ`(n)

Recurrence tree for T(n/5) + T(7n/10) + `Θ`(n)

Here, the base case ≤ n.
The base case is a range n ≤ nₒ rather than a single value because:

Imperfect division: Subproblem sizes may not be exact integers (e.g., n/5 or 7n/10 may round), so recursion can land on any small integer. A range ensures all small values are handled.
Asymptotic equivalence: Any constant-sized input takes constant time (Θ(1)), so stopping at any small n ≤ nₒ does not affect the overall Big-O.

Since each step reduces the total problem size (n/5 + 7n/10 = 9n/10 < n), the recursion eventually reaches this small range, guaranteeing termination.

The height of the tree

The height of a recursion tree is determined by the longest path from the root (the initial problem of size n) to a leaf (the base case). Each level of the tree represents a recursive call.

Left Branch: The term T(n/5) reduces the problem size by a factor of 5 at each step. The size of the problem on this path increases as follows: n → n/5 → n/25 → ...
Right Branch: The term T(7n/10) reduces the problem size by a factor of 10/7 ≈ 1.43 at each step. The size of the problem on this path goes n → 7n/10 → 49n/100 → …

Since the problem size on the right side of the tree decreases much more slowly than on the left side, it will take more recursive calls (i.e., more levels in the tree) for the T(7n/10) branch to reach the base case. Therefore, this path will be the longest, dictating the overall height of the tree.

Mathematically, the depth dof a branch is found when the problem size becomes a constant (e.g., 1).

Left path depth: (1/5)ᵈ.n = 1 ⇒ d = log₅n
Right path depth: (7/10)ᵈ.n = 1 ⇒ d = log₁₀⸝₇ n

Since the base of the logarithm is smaller for the right path (10/7 ≈ 1.43 is smaller than 5), log₁₀⸝₇ n is a larger value than log₅n. This confirms the right side is taller.

Recursion Tree Analysis

Level 0 (Root): The work done at the top level is simply cn.
Level 1: The problem is split into two subproblems of sizes n/5 and 7n/10. The work done for these subproblems is c(n/5) and c(7n/10). The total cost for this level is: c(n/5) + c(7n/10) = c(9n/10)
Level 2: The work done at the next level will be (9/10) of the work at Level 1, which is (9/10)²cn.

This reveals a pattern: the cost at any level i is (9/10)ⁱ cn.

Lower bound: T(n) ≥ cn
The total work T(n) must be at least the work done at the root of the recursion tree, which is cn. This simple observation establishes a lower bound for the recurrence, proving that T(n)=Ω(n)

Upper bound: T(n) ≤ c₁⋅(number of base cases) + total cost at all levels
T(n) ≤ c₁. number of base cases + Total cost at all levels
T(n) ≤ c₁ . number of base cases + [cn + (9/10)cn + (9/10)²cn + (9/10)³cn + …]
The total cost is the sum of the work at the leaves (base cases) plus the work at all the internal recursive levels (the series).
Total cost at all levels = cn + (9/10)cn + (9/10)²cn + (9/10)³cn + … is a geometric series with ratio r = 9/10 < 1. Hence the sum is, 1/ 1 — (9/10) , i.e.,
T(n) ≤ c₁ . number of base cases + [cn + (9/10)cn + (9/10)²cn + (9/10)³cn + …]
T(n) ≤ c₁n + [1/ 1 — (9/10)]
T(n) ≤ c₁n + 10cn
T(n) ≤ c₂n
This proves that the cost of all the recursive levels is bounded by c₂n, which means it is O(n)

Get Prajun Trital’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

We established a lower bound: T(n)=Ω(n).
We established an upper bound: T(n)=O(n).
When a function is both Ω(n) and O(n), its tight bound is Θ(n).
Hence, T(n) = Θ(n)

Example: T(n) = 3T(n/2) + cn

Here cn is Θ(n)

We keep dividing the sub-problem by 2 (i.e., b), so n = 2ᵏ, which also means k = log₂n.
Here, k represents the number of times we can halve the input before we get down to a single element.

2ᵏ (or n): This is the size of the original problem at the root of the recursion tree. At this top level, there is 1 (3⁰) problem.
2ᵏ⁻¹ (or n/2): After the first recursive call, the problem is split. This is the size of a subproblem at the first level of recursion. At this level, there are 3 (3¹) such subproblems.
2ᵏ⁻² (or n/4): At the second level of recursion, the problem is halved again. At this level, there are 9 (3²) subproblems of this size.
And so on…: This pattern continues. At any level i, the size of a subproblem is 2ᵏ⁻ⁱ, and the number of subproblems is 3ⁱ.
2¹ (or 2): This represents a very small subproblem near the end of the process, typically the last step before hitting the base case. At this level (k−1), there would be 3ᵏ⁻¹ such problems.
2⁰ (or 1): This is the base case of the recursion. A problem of size 1 is trivial to solve (e.g., an array with one element is already sorted), and the recursion stops here. This final level (k) is the “leaf level,” and it contains a total of 3ᵏ(or nˡᵒᵍ₂³) subproblems.

In the general form of a divide-and-conquer recurrence, T(n)= aT(n/b) + f(n), the coefficient a represents the number of subproblems, while the term n/b inside the recursive call defines the size of each subproblem.

Recursion Tree Analysis

Level 0: 1 node (3⁰) → cost = cn
Level 1: 3 nodes (3¹), each with a subproblem of size n/2 → total cost = 3⋅c(n/2)=(3/2)cn
Level 2: 9 nodes (3²), each with a subproblem of size n/4 → total cost = 9⋅c(n/4) = (9/4)cn = (3/2)²cn
Pattern: The cost of Leveli is (3/2)ⁱ cn.

Height of the Tree
The height of the recursion tree is determined by the number of times the problem size can be divided by 2 until it reaches 1.
n/2ʰ = 1 ⟹ h = log₂n

Cost of the Leaves
The number of leaves is the number of nodes at the last level, which is 3ʰ, or 3ˡᵒᵍ₂ⁿ. Using the logarithm identity a⁽ˡᵒᵍᵦ c⁾ = c⁽ˡᵒᵍᵦ a⁾, this becomes nˡᵒᵍ₂³. Since each leaf has a constant cost T(1), the total cost of the leaves is Θ(nˡᵒᵍ₂3). This is a precise calculation, so the tight bound notation (Θ) is appropriate.

In this case, the level cost varies across levels, so the total cost cannot be obtained by simply multiplying the cost per level by the height. Instead, the total cost is found by summing the costs of all levels in the tree.

The total cost is the sum of the costs of all recursive levels plus the cost of the leaves.

The exponent **log2**`₂`**n − 1** represents the index of the last recursive level before reaching the leaves at level h = log`₂`n.

We can factor out cn to see the structure more clearly:

Solving the sequence

The series ratio r = 3/2>1. Since the ratio is greater than 1, the sum increases at each step. This means the cost is leaf-heavy; the bulk of the work is done at the bottom of the tree.

Applying the finite geometric series formula

The denominator:
3 / 2 -1 = 1/2

The numerator:
We need to simplify the term (3/2)ˡᵒᵍ₂ⁿ.

The denominator is simple: 2`ˡᵒᵍ₂ⁿ` = n. For the numerator, we use the log identity `a⁽ˡᵒᵍᵦ c⁾ = c⁽ˡᵒᵍᵦ a⁾, 3ˡᵒᵍ₂ⁿ = nˡᵒᵍ₂³`

So the full term becomes: nˡᵒᵍ₂³/n

Putting it all together, the value of the sum.

Now, substituting the sum into the T(n)

This final expression consists of two terms, 2c⋅`nˡᵒᵍ₂³` and 2cn. Since log`₂`3 ≈ 1.58, the `nˡᵒᵍ₂³` term grows much faster and dominates the expression.

Therefore, the total cost of the internal nodes is Θ(nˡᵒᵍ₂³). This confirms our earlier conclusion: the work is leaf-heavy, and the total cost is asymptotically the same as the cost of the leaves.
Hence T(n) = Θ(nˡᵒᵍ₂³)

Analysis of Recursion Tree Costs

This analysis outlines three distinct scenarios in divide-and-conquer algorithms, categorized by where the computational work is concentrated within the recursion tree.

Case I: Leaf-Heavy (Bottom-Heavy) 🔺

Recurrence Example: T(n) = 3T(n/2) + cn
Analysis: The algorithm creates more subproblems than the rate at which their size shrinks (e.g., 3 subproblems, each half the size). This causes the total work to increase at each level of recursion. The majority of the work is performed at the leaves of the tree, making the final complexity dependent on the number of leaves.
Complexity: Θ(nˡᵒᵍ₂³) ≈ Θ(n¹˙⁵⁸)

Case II: Balanced ⚖️

Recurrence Example: T(n) = 2T(n/2) + cn
Analysis: The rate of creating new subproblems is perfectly balanced by the rate at which their size decreases (e.g., 2 subproblems, each half the size). As a result, the work done is the same at every level. The total cost is determined by the work per level multiplied by the height of the tree.
Complexity: Θ(nlogn)

Case III: Root-Heavy (Top-Heavy) 🔻

Recurrence Example: T(n)=T(n/2) + cn
Analysis: This scenario involves creating fewer subproblems than the rate of size reduction (e.g., 1 subproblem, half the size). The work decreases at each level, so the initial work at the root dominates the total cost.
Complexity: Θ(n)

These three cases lead us to the Master Method/Theorem.

Master Method/Theorem

The Master Theorem is a shortcut for solving divide-and-conquer recurrence relations that fit the specific form:
T(n) = aT(n/b) + f(n)

where:

a ≥ 1 is the number of subproblems.
b > 1 is the factor by which the input size is reduced.
The term n/b tells us how the problem size is reduced at each step.
f(n) is the work done to divide the problem and combine the results. i.e., the level cost

Subproblem Size and Tree Height

The height depends on how quickly the problem size shrinks at each level. The term n/b from the Master Theorem dictates how the problem size is reduced at each step.

Tracking the size of a single subproblem as it goes down the levels of the recursion tree reveals a clear pattern:

Level 0 (Root): The size of the original problem is n.
Level 1: The size of a subproblem is n/b.
Level 2: The size of a subproblem is (n/b)/b = n/b².
Level i (General Case): At any level i, the size of a subproblem is n/bⁱ.

This process of division continues until the subproblem size becomes a small constant (like 1), which is the base case where the recursion stops.

The `n = bᵏ` Assumption

To find the height of the tree, the question to answer is: “How many times can the size n be divided by b until it reaches 1?”
To make this calculation simple, it is helpful to assume that n is a perfect power of b. This is expressed with the relationship: n = bᵏ

In this setup, k is exactly the number of division steps needed, meaning k represents the height of the tree. This gives a direct formula for the height (h), i.e.,

Here, k represents the **height of the recursion tree.**

Press enter or click to view image in full size

Height of the tree (h)

This assumption also allows for a clean expression of the size at each level using powers of b:

At Level 0 (Root): The size is bᵏ
At Level 1, the size is bᵏ⁻¹
At Level 2, the size is bᵏ⁻²
…
At Level k-1 (Second to Last), the size is bᵏ⁻⁽ᵏ⁻¹⁾ = b¹
At Level k (Base Level), the size is bᵏ⁻ᵏ= b⁰ = 1

Number of Base Cases (Leaves)

The base cases are the leaf nodes at the bottom of the recursion tree. Their number depends on the branching factor (a) and the height (h).

At Level 0, there is 1 = a⁰ node.
At Level 1, there are a¹ nodes.
At Level h, there are aʰ nodes.

Since the leaves are at the last level (h), the number of base cases is aʰ

By substituting h, we get the final formula for the number of leaves.

Using a common logarithm identity, this can be rewritten as nˡᵒᵍbᵃ

The Three Cases of the Master Theorem

Case I: Leaf-Heavy (Bottom-Heavy) 🔺
The work at the leaves of the recursion tree dominates the total cost.

Condition: The function f(n) is polynomially smaller than 𝑛ˡᵒᵍbᵃ (Formally: f(n) = O(𝑛ˡᵒᵍbᵃ⁻𝜖) for some constant ϵ > 0)
Solution: T(n) = Θ(𝑛ˡᵒᵍbᵃ)
Example: T(n) = 3T(n/2) + n, here f(n) = n
- Here, 𝑛ˡᵒᵍbᵃ= nˡᵒᵍ₂³ ≈ Θ(n¹˙⁵⁸)
- Since f(n) = n is polynomially smaller than n¹˙⁵⁸
- The solution is Θ(nˡᵒᵍ₂³)

Case II: Balanced ⚖️
The work is distributed evenly across all levels of the tree.

Condition: The function f(n) is asymptotically equal to 𝑛ˡᵒᵍbᵃ (Formally: f(n) = Θ(𝑛ˡᵒᵍbᵃ))
Solution: T(n) = Θ(𝑛ˡᵒᵍbᵃ lgn)
Example: T(n) = 2T(n/2) + n, here f(n) = n
- Here, 𝑛ˡᵒᵍbᵃ = nˡᵒᵍ₂² = n¹.
- This is asymptotically the same as f(n) = n
- The solution is Θ(nlgn)

Case III: Root-Heavy (Top-Heavy) 🔻
The work done at the root, f(n), dominates the total cost.

Condition 1: The function f(n) is polynomially larger than 𝑛ˡᵒᵍbᵃ (Formally: f(n) = Ω(𝑛ˡᵒᵍbᵃ+ 𝜖) for some constant ϵ>0)
Condition 2 (Regularity Check): The work must decrease at each level by a constant factor.
(Formally: a f(n/b) ≤ c f(n) for some constant c < 1 and large n)
Solution: T(n) = Θ(f(n))
Example: T(n) = 3T(n/4) + n², here f(n) = n²
- Here, 𝑛ˡᵒᵍbᵃ = 𝑛ˡᵒᵍ₄³ ≈ n⁰˙⁷⁹
- f(n) = n² is polynomially larger than n⁰˙⁷⁹
- We check the regularity condition: 3⋅c(n/4)² = (3/16) cn².
Since 3/16 < 1
- The solution is Θ(n²)

Implications of the Master Theorem

Application of the Master Theorem

T(n) = 9T(n/3) + n

2. T(n) = T(2n/3) + 1

3. T(n) = 3T(n/4) + nlgn

Exception to Master Theorem

nlgn is logarithmically larger than n, not polynomially. So, we can’t use Master Theorem

This example demonstrates an example of a recurrence relation where the Master Theorem cannot be applied. It falls into a “gap” between the defined cases.

The Comparison: The Master Theorem works by comparing the function f(n) with the term 𝑛ˡᵒᵍbᵃ. For this problem, we are comparing:
- f(n) = nlgn
- 𝑛ˡᵒᵍbᵃ = 𝑛ˡᵒᵍ₂² = n¹
Checking the Cases
- It’s not Case 1 or 2 because f(n)=nlgn is asymptotically larger than n.
- The next logical step is to check Case 3. However, Case 3 requires f(n) to be polynomially larger than n.
The “Polynomial” Test
To be polynomially larger, the ratio between the two functions must grow faster than a constant, specifically by a factor of n^ϵ.

The difference between the two functions is only a **logarithmic factor**. A logarithmic function (lgn) always grows slower than any polynomial function (n^ϵ, for any ϵ>0).

Since the difference is not polynomial, the condition for Case 3 is not met. The recurrence falls into the gap between Case 2 and Case 3, meaning a different method (like the recursion-tree method) is needed to solve it. We will get T(n) = θ(nlog²n) if we solve using a recursive tree method.