Coursify

Complexity Analysis of a Divide-and-Conquer Recurrence

Complexity Analysis of a Divide-and-Conquer Recurrence

Verified Sources
May 26, 2026

In the analysis of divide-and-conquer algorithms, we frequently encounter equations called recurrence relations . These relations describe the running time of an algorithm in terms of its execution time on smaller inputs.

Consider the following recurrence relation:

T(n)=2T(n/4)+n2log⁡nT(n) = 2T(n/4) + n^2 \log n

This equation characterizes an algorithm that divides a problem of size nn into 22 subproblems of size n/4n/4, solving them recursively, and combines the results in n2log⁡nn^2 \log n non-recursive step time. To find the asymptotic complexity of this recurrence, we can visualize the execution flow using a recursion tree:

To solve this systematically, we can apply the Master Theorem .

Footnotes

  1. Recurrence Relations - GeeksforGeeks - Complete guide on solving recurrence relations using recursion trees, substitution, and master methods. ↩

  2. Master Theorem (Analysis of Algorithms) - Wikipedia - Comprehensive overview of the Master Theorem's history, cases, and mathematical formulations. ↩

Master Theorem for Divide-and-Conquer Recurrences

The Master Theorem Framework

The standard Master Theorem is used to solve divide-and-conquer recurrences of the form T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n), where a≥1a \ge 1 is the number of subproblems, b>1b > 1 is the factor by which the subproblem size is reduced, and f(n)f(n) is the cost of the work done outside the recursive calls .

Footnotes

  1. Master Theorem (Analysis of Algorithms) - Wikipedia - Comprehensive overview of the Master Theorem's history, cases, and mathematical formulations. ↩

Evaluating the Recurrence Step-by-Step

  1. 1
    Step 1

    From the given recurrence relation T(n)=2T(n/4)+n2log⁡nT(n) = 2T(n/4) + n^2 \log n, we identify the parameters:

    • a=2a = 2 (number of subproblems)
    • b=4b = 4 (subproblem size division factor)
    • f(n)=n2log⁡nf(n) = n^2 \log n (non-recursive work) .

    Footnotes

    1. Recurrence Relations - GeeksforGeeks - Complete guide on solving recurrence relations using recursion trees, substitution, and master methods. ↩

  2. 2
    Step 2

    Next, we compute the critical exponent which determines the growth rate of the leaves in the recursion tree: log⁡ba=log⁡42=0.5\log_b a = \log_4 2 = 0.5 This means the number of leaves grows at a rate of n0.5=nn^{0.5} = \sqrt{n} .

    Footnotes

    1. CLRS Solutions | Exercise 4.5-1 | Divide-and-Conquer - Detailed textbook solutions illustrating Case 3 Master Method application for quadratic polynomial overheads. ↩

  3. 3
    Step 3

    We compare the non-recursive term f(n)=n2log⁡nf(n) = n^2 \log n with the leaf growth term nlog⁡ba=n0.5n^{\log_b a} = n^{0.5}:

    • f(n)=Ω(n0.5+ϵ)f(n) = \Omega(n^{0.5 + \epsilon}) for any ϵ≤1.5\epsilon \le 1.5.
    • This indicates that the non-recursive work at the root level dominates the overall work, pointing toward Case 3 of the Master Theorem .

    Footnotes

    1. Master Theorem (Analysis of Algorithms) - Wikipedia - Comprehensive overview of the Master Theorem's history, cases, and mathematical formulations. ↩

  4. 4
    Step 4

    For Case 3 to apply, we must satisfy the [regularity condition]{def="A mathematical constraint in Case 3 of the Master Theorem requiring af(n/b) <= cf(n) for some constant c < 1"} for some constant c<1c < 1 and all sufficiently large nn: af(n/b)≤cf(n)a f(n/b) \le c f(n) Substituting our parameters: 2((n4)2log⁡(n4))≤cn2log⁡n2 \left( \left(\frac{n}{4}\right)^2 \log\left(\frac{n}{4}\right) \right) \le c n^2 \log n 18n2(log⁡n−log⁡4)≤cn2log⁡n\frac{1}{8} n^2 (\log n - \log 4) \le c n^2 \log n Choosing c=1/8=0.125<1c = 1/8 = 0.125 < 1 satisfies this condition for all n≥4n \ge 4 .

    Footnotes

    1. CLRS Solutions | Exercise 4.5-1 | Divide-and-Conquer - Detailed textbook solutions illustrating Case 3 Master Method application for quadratic polynomial overheads. ↩

  5. 5
    Step 5

    Since Case 3 is verified, the non-recursive work f(n)f(n) dominates the recurrence. Thus, the overall time complexity is: T(n)=Θ(f(n))=Θ(n2log⁡n)T(n) = \Theta(f(n)) = \Theta(n^2 \log n) This matches option (iii) .

    Footnotes

    1. Master Theorem: Practice Problems and Solutions - University of Western Ontario - Academic problem set demonstrating the application of various Master Theorem cases to recurrence relations. ↩

The Power of Dominance

Whenever the non-recursive cost f(n)f(n) is polynomially larger than the leaf cost nlog⁡ban^{\log_b a}, the root level does almost all the work. The work decreases geometrically as you go down the tree, meaning the total time complexity is simply determined by the root's cost, T(n)=Θ(f(n))T(n) = \Theta(f(n)) .

Footnotes

  1. Master Theorem: Practice Problems and Solutions - University of Western Ontario - Academic problem set demonstrating the application of various Master Theorem cases to recurrence relations. ↩

Comparison of Leaf Cost vs. Non-Recursive Cost

Visualizing the divergence between leaf cost sqrt(n) and non-recursive cost n^2 log n

Mathematical Proofs and Alternative Methods

Knowledge Check

Question 1 of 3
Q1Single choice

What is the correct asymptotic complexity of the recurrence relation T(n)=2T(n/4)+n2log⁡nT(n) = 2T(n/4) + n^2 \log n?

Explore Related Topics

1

Complexity Analysis: Best Case, Worst Case, and Average Case

The material introduces best‑case, worst‑case, and average‑case complexity as three distinct functions describing an algorithm’s running time on inputs of size nn, explains how they are formally defined, and shows why worst‑case analysis is usually preferred.

  • Best case: Tbest(n)=min⁡I∈InT(I)T_{\text{best}}(n)=\min_{I\in\mathcal I_n} T(I), the minimum time over all inputs of size nn.
  • Worst case: Tworst(n)=max⁡I∈InT(I)T_{\text{worst}}(n)=\max_{I\in\mathcal I_n} T(I), giving a guaranteed upper bound.
  • Average case: Tavg(n)=∑I∈InP(I) T(I)T_{\text{avg}}(n)=\sum_{I\in\mathcal I_n}P(I)\,T(I), requiring an explicit input probability model.
  • Linear search illustrates the three cases: Θ(1)\Theta(1) best, Θ(n)\Theta(n) worst, and Θ(n)\Theta(n) average (expected n+12\frac{n+1}{2} comparisons).
  • Worst‑case analysis is favored because it needs no probabilistic assumptions and ensures reliability for all inputs, especially in real‑time or safety‑critical systems.
2

Counting Relations on a Set with $n$ Elements

3

Mastering Recurrence Relations: The Substitution Method

The lesson shows how to solve the classic recurrence T(n)=2T(n/2)+nT(n)=2T(n/2)+n with the substitution method, using a recursion‑tree intuition to guess an O(nlog⁡n)O(n\log n) bound and then proving it by induction.

  • Each level of the recursion tree costs nn, and there are log⁡2n\log_2 n levels → total Θ(nlog⁡n)Θ(n\log n).
  • Inductive hypothesis: T(n)≤c nlog⁡2nT(n)\le c\,n\log_2 n for n≥n0n\ge n_0, which simplifies to c≥1c\ge1 in the induction step.
  • The base case must start at n0>1n_0>1 (e.g., n0=2n_0=2) because T(1)≤c⋅1log⁡21T(1)\le c\cdot1\log_2 1 is false.
  • Substitution offers rigorous proof, while recursion trees give quick guesses; the Master Theorem confirms T(n)=Θ(nlog⁡n)T(n)=Θ(n\log n).
Browse all research articles