Recurrence Relations for GATE CSE: Master Theorem and More

Recurrence relations are asked in almost every GATE CSE paper, and the papers deliberately choose the forms the Master theorem does not cover. This guide sets out the three Master cases and where they stop applying, then the substitution and recursion-tree methods that handle the rest, with one short example each.

Key takeaways

• Recurrences score 85.5 out of 100 in the book's evidence model, fourth among algorithm concepts and inside the Very High band.
• The Master theorem needs a polynomial gap between the driving function and the critical exponent. Two of GATE's favourite recurrences sit in the gap.
• Subtract-and-conquer forms, unequal splits and square-root recurrences are outside the Master theorem entirely.
• The recent format is a numeric answer asking for the exponent, which carries no negative marking.
• Counting recurrences from discrete mathematics use characteristic equations and are a separate skill.

Where recurrences sit in the paper

The official Algorithms syllabus line names asymptotic worst case time and space complexity along with divide-and-conquer as a design technique, which is where recurrences enter. Separately, the Engineering Mathematics line names recurrence relations under combinatorics.

Analyst compilations, which are not official and differ by 2 to 3 marks between sources, put Algorithms at roughly 8.3 marks per paper averaged over 2009 to 2026, with a reported range of about 6 to 11. Within that, expect one recurrence or loop-complexity item per shift. The reconstructed record lists Master-theorem forms in 2002, 2004 to 2006, 2008, 2009, 2012, 2014 to 2017, 2019 to 2021, and 2023 to 2026, and non-standard substitution forms across a similar spread.

The Master theorem, stated for the exam

For a recurrence where a subproblems of size n over b are solved plus a driving cost, let the critical exponent be the logarithm of a to the base b.

• Case 1. The driving cost is smaller than the critical power by a polynomial factor. The answer is the critical power.
• Case 2. The driving cost matches the critical power up to a log factor raised to some power k at least 0. The answer gains one more log.
• Case 3. The driving cost is larger than the critical power by a polynomial factor, and a regularity condition holds. The answer is the driving cost.

Worked example for Case 1: eight subproblems of half size with a quadratic driving cost. The critical exponent is the logarithm of 8 to base 2, which is 3. The driving cost is a lower power, so the answer is n cubed and the numeric answer for the exponent is 3.

Where the Master theorem stops

The word "polynomial" in Cases 1 and 3 is the whole exam. A gap of a log factor is not polynomial, so those recurrences fall into the extended Case 2 or out of the theorem altogether.

The first two rows are the boundary cases. Two halves plus n log n is Case 2 with the log exponent equal to 1, so the solution picks up a second log. Two halves plus n over log n sits at the exponent minus one boundary, where the sum of the levels is a harmonic series rather than a geometric one, and the answer is n log log n rather than a clean n.

Substitution and change of variable

When the subproblem size does not shrink by a constant factor, expand the recurrence a few levels and find the pattern.

For a recurrence that reduces the size by one and adds n each time, expanding gives the sum of the first n integers, which is quadratic. Reducing by one and adding log n gives the log of n factorial, which is n log n. Reducing by one with two recursive calls and a constant doubles the work each level and gives 2 to the n.

For square-root steps, change the variable. Write the input as 2 raised to some power m. A step down to the square root halves m, so the recurrence becomes a halving one with constant work, whose solution is the log of m. Substituting back, m is the log of n, so the answer is log log n.

The book works through all of these forms with practice questions built around the shapes that have recurred, and ranks recurrences alongside the other 27 algorithm concepts on the same evidence model.

Recursion trees for unequal splits

When the two subproblems have different sizes, draw the tree and read off the cost per level. For a recurrence that splits into one third and two thirds with a linear driving cost, every level costs about n until branches start bottoming out. The shortest root-to-leaf path has length log to base 3 of n, and the longest has length log to base 3 over 2 of n. Both are proportional to log n, so the total is n log n.

The same reading handles a split into one half and one quarter with a linear cost. The per-level cost now shrinks geometrically, by three quarters each level, so the sum is dominated by the root and the answer is linear in n.

The rule to remember from these two: when the per-level cost is constant, multiply it by the number of levels; when it shrinks geometrically, the root dominates; when it grows geometrically, the leaves dominate.

Counting recurrences from discrete mathematics

The other family is asked under combinatorics, where you are given a linear recurrence with constant coefficients and asked for a closed form or a specific term. The method is the characteristic equation.

Suppose a sequence satisfies the rule that each term is five times the previous minus six times the one before, with the first two terms 1 and 4. The characteristic equation has roots 2 and 3, so the closed form combines 2 to the n and 3 to the n. Fitting the two starting values gives twice 3 to the n minus 2 to the n. Checking the third term, twice 9 minus 4 is 14, which matches five times 4 minus six times 1.

Repeated roots change the shape: the closed form then multiplies one of the terms by n. The usual slips are a sign error in the characteristic equation and confusing which starting index the question uses. Counting problems, such as the number of binary strings with no two consecutive ones, reduce to this family after you set up the recurrence yourself, which is the harder half of the work.

How to practise recurrences

Keep the table above on one page and rewrite it from memory every week until the boundary rows are automatic. Then practise in the paper's own format, which is increasingly a numeric answer for an exponent or for a specific term rather than a choice among four asymptotic forms.

For the wider subject, the priorities and the other algorithm patterns are in Algorithms important topics; the counting side is covered in the Discrete Mathematics guide; the standard solutions are collected in the GATE CSE formula sheet; and the wrong answers built into past distractors are catalogued in the common mistakes guide.