Divide and Conquer for GATE: Recurrence Analysis of Merge Sort, Quick Sort and Binary Search

Knowing that Merge Sort takes Theta(n log n) is not enough for a recurrence question. GATE can change the split, the combine cost or the pivot behaviour, and a memorised answer then stops helping.

The reliable method is to translate the algorithm into split, solve and combine work. Once the recurrence is correct, its asymptotic solution usually becomes routine.

1. The divide-and-conquer template and its recurrence

A divide-and-conquer algorithm has three stages:

1. Divide a problem of size n into smaller subproblems.

2. Solve those subproblems recursively.

3. Combine their answers, or do the non-recursive work around them.

If there are a subproblems, each of size n/b, and the divide-plus-combine work is f(n), the recurrence is:

T(n) = aT(n/b) + f(n)

Each symbol comes from the code, not from a formula sheet. Count the recursive calls to get a, read the new input size to get b, and count the work outside those calls to get f(n).

The standard shapes are:

That last recurrence is not in Master Theorem form because its subproblem is n-1, not n/b for a constant b > 1.

2. The Master Theorem: the watershed term and its three cases

For T(n) = aT(n/b) + f(n), first compute the watershed term:

n^(log_b a)

Then compare f(n) with it.

• Case 1: f(n) is polynomially smaller. The recursive leaves dominate, so T(n) = Theta(n^(log_b a)).

• Case 2: f(n) matches the watershed term, possibly with a logarithmic factor. For the basic equal case, T(n) = Theta(n^(log_b a) log n).

• Case 3: f(n) is polynomially larger and the regularity condition holds. The root-side work dominates, so T(n) = Theta(f(n)).

The phrase “polynomially smaller” matters. A logarithmic gap is not automatically Case 1. The complete case boundaries and regularity condition are worked through in Master Theorem for GATE.

3. Worked example: Merge Sort recurrence and count

Merge Sort creates two half-size recursive calls and merges their sorted results in linear time:

T(n) = 2T(n/2) + n

Here a = 2, b = 2, and f(n) = n.

n^(log_b a) = n^(log_2 2) = n

The combine work equals the watershed term, so basic Case 2 applies:

T(n) = Theta(n log n)

Now take eight elements: [5, 2, 4, 7, 1, 3, 2, 6]. There are log_2 8 = 3 merge levels above the singleton base cases. Under the recurrence's linear-work model, each level contributes n = 8 work units:

Level work total = 8 + 8 + 8 = 3 x 8 = 24

n log_2 n = 8 x 3 = 24

This 24 is a level-work model, not the exact number of key comparisons. For this particular list, a direct trace gives 5 comparisons in the left half, 5 in the right half and 7 in the final merge, for 17 exact comparisons. Keeping those two counts separate prevents an easy conceptual error.

4. Worked example: Quick Sort best versus worst

When the pivot splits the input into two equal halves, Quick Sort has the same broad recurrence as Merge Sort:

T(n) = 2T(n/2) + n = Theta(n log n)

The result follows from Case 2. The partition work is linear at each of Theta(log n) balanced levels.

In the degenerate case, such as repeatedly choosing the smallest element as pivot on an already sorted input, one side has size zero and the other has size n-1:

T(n) = T(n-1) + n

Unroll it:

T(n) = n + (n-1) + (n-2) + ... + 1

T(n) = n(n+1)/2 = Theta(n^2)

For n = 5, this particular recurrence model gives 5 + 4 + 3 + 2 + 1 = 15 work units. If the question asks specifically for key comparisons in a conventional partition, the partition on size k makes k-1 comparisons. That exact count is:

4 + 3 + 2 + 1 = 10 comparisons

Read what the stem counts. “Operations according to the recurrence” and “key comparisons” need not be the same number. For a broader comparison of stability, space and best-to-worst behaviour, use Sorting Algorithms: Comparison and Complexity.

5. Worked example: Binary Search recurrence

Binary Search examines the middle element and continues in only one half. The comparison and index update outside the recursive call take constant time:

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

Here a = 1, b = 2, and f(n) = 1.

n^(log_b a) = n^(log_2 1) = n^0 = 1

Again the two terms match, so Case 2 gives:

T(n) = Theta(log n)

For n = 1000, the maximum number of probes is:

floor(log_2 1000) + 1 = floor(9.965...) + 1 = 10

You can check this without a calculator. Since 2^9 = 512 is below 1000 and 2^10 = 1024 is above it, ten probes are enough to isolate any one of 1000 positions, and nine are not.

6. Traps and how GATE tests recurrence analysis

• Do not apply the Master Theorem to T(n) = T(n-1) + n. It is outside the required n/b shape.

• T(n) = 2T(n/2) + n/log n falls into a logarithmic gap not covered by the basic three-case statement. A recursion tree settles it: level i carries n/(log n - i) work, and that harmonic sum gives Theta(n log log n). Substitution or Akra-Bazzi reaches the same answer.

• The f(n) term is work at one node. Total non-recursive work must be summed across every node and level.

• Quick Sort is not unconditionally Theta(n log n). A balanced split has that order, a degenerate split has Theta(n^2), and randomised pivoting gives expected Theta(n log n) under the usual assumptions.

• A recursion-tree level count and an exact comparison count answer different questions. State which one you are calculating.

In the paper this shows up in three recognisable forms: a code fragment you must convert into T(n) yourself, a stated recurrence with four asymptotic options, and a numerical-answer stem asking for an exact count at a small n. The first two reward the a, b, f(n) reading above. The third is where the modelled-work versus exact-comparison distinction decides the mark. For the syllabus, subject weightage and paper structure, check the official GATE portal; the recurrences themselves do not change with the exam year.

7. Short version and next step

Write T(n) = aT(n/b) + f(n), compute n^(log_b a), and only then choose the Master Theorem case. Merge Sort and balanced Quick Sort are Theta(n log n), degenerate Quick Sort is Theta(n^2), and Binary Search is Theta(log n).

Build speed by solving fresh recurrences, not by rereading the final orders. Follow the analysis sequence in GATE Guidance by Sanchit Sir, practise under time pressure in the GATE Test Series, and use the GATE preparation category for the surrounding Algorithms topics.