Substitution Method MCQs: 12 Solved GATE and ISRO Questions with Explanations

Recurrence questions look scary on a GATE paper, but most fall to one tool: expand a few steps, spot the pattern, sum it, and stop at the base case. That is the substitution method, and GATE papers from 1999 to 2025 and ISRO papers from 2011 to 2017 have asked recurrences that yield to it.

Related reading: recurrence relations and algorithm design methods.

The substitution method in 60 seconds

Use the same four steps each time:

1. Write T(n) in terms of a smaller input.

2. Expand two or three levels.

3. Generalise the expression after k levels.

4. Choose k to reach the base case, then sum what remains.

For a warm-up, take T(n) = T(n-1) + n, with T(1) = 1:

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

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

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

After k steps, T(n) = T(n-k) plus the top k terms. At k = n-1, T(n) = 1 + 2 + 3 + ... + n = n(n+1)/2 = Theta(n^2).

Arithmetic series usually produce polynomial growth. Geometric series usually produce exponential growth.

Subtract-and-conquer recurrences: expand and sum (Q1-Q3)

Q1. ISRO 2011

"Let T(n) be defined by T(1) = 10 and T(n + 1) = 2n + T(n) for all integers n >= 1. Which of the following represents the order of growth of T(n) as a function of n?" (a) O(n) (b) O(n log n) (c) O(n^2) (d) O(n^3).

Answer: (c) O(n^2). Unrolling gives T(n) = 10 + 2(1 + 2 + ... + n-1) = 10 + n(n-1). The constant 10 does not affect the quadratic order. Open Q1 in the solved question bank.

Q2. GATE 2004

"The recurrence equation T(1) = 1, T(n) = 2T(n - 1) + n, n >= 2 evaluates to" (a) 2^(n+1) - n - 2 (b) 2^n - n (c) 2^(n+1) - 2n - 2 (d) 2^n + n.

Answer: (a) 2^(n+1) - n - 2. The recurrence gives T(2) = 2(1) + 2 = 4 and T(3) = 2(4) + 3 = 11. Option (a) gives 8 - 2 - 2 = 4 and 16 - 3 - 2 = 11. Only it survives both checks. Open Q2 in the solved question bank.

Q3. GATE 2025

"Consider the following recurrence relation: T(n) = 2T(n - 1) + n 2^n, for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?" (a) T(n) = Theta(n^2 2^n) (b) T(n) = Theta(n 2^n) (c) T(n) = Theta((log n)^2 2^n) (d) T(n) = Theta(4^n).

Answer: (a) Theta(n^2 2^n). Divide by 2^n and define S(n) = T(n)/2^n. Then S(n) = S(n-1) + n. This is the warm-up recurrence, so S(n) = Theta(n^2) and T(n) = Theta(n^2 2^n). Open Q3 in the solved question bank.

Geometric growth: multiplying recurrences (Q4-Q5)

Q4. GATE 2024

"Let T(n) be the recurrence relation defined as follows: T(0) = 1, T(1) = 2, and T(n) = 5T(n - 1) - 6T(n - 2) for n >= 2. Which one of the following statements is TRUE?" (a) T(n) = Theta(2^n) (b) T(n) = Theta(n 2^n) (c) T(n) = Theta(3^n) (d) T(n) = Theta(n 3^n).

Answer: (a) Theta(2^n). The equation x^2 - 5x + 6 = 0 has roots 2 and 3, so T(n) = A 2^n + B 3^n. Now A + B = 1 and 2A + 3B = 2, giving B = 0 and A = 1. Thus T(n) is exactly 2^n, despite the larger root. Open Q4 in the solved question bank.

Q5. GATE 2002

"The solution to the recurrence equation T(2^k) = 3T(2^(k-1)) + 1, T(1) = 1, is:" (a) 2^k (b) (3^(k+1) - 1)/2 (c) 3 log2 k (d) 2 log3 k.

Answer: (b) (3^(k+1) - 1)/2. Put t(k) = T(2^k). Then t(k) = 3t(k-1) + 1, so t(k) = 3^k t(0) + (3^(k-1) + ... + 3 + 1). Since t(0) = T(1) = 1, this becomes 3^k + (3^k - 1)/2 = (3^(k+1) - 1)/2. At k = 1, both the recurrence and formula give T(2) = 4. Open Q5 in the solved question bank.

Square-root recurrences: change the variable (Q6-Q8)

When the input becomes sqrt(n), count square roots to a constant. From 2^16, the inputs are 2^8, 2^4, 2^2, and 2^1. That is four steps, matching log2 log2 2^16 = log2 16 = 4.

Q6. GATE 2007

"What is the time complexity of the following recursive function:"

int DoSomething (int n)
{
  if (n <= 2)
    return 1;
  else
    return (DoSomething (floor(sqrt(n))) + n);
}

(a) Theta(n) (b) Theta(n log n) (c) Theta(log n) (d) Theta(log log n).

Answer: (d) Theta(log log n). Its running-time recurrence is T(n) = T(sqrt(n)) + Theta(1). After k square roots, log n has been halved k times, so the base case arrives after Theta(log log n) levels. Open Q6 in the solved question bank.

Q7. GATE 2020

"For parameters a and b, both of which are omega(1), T(n) = T(n^(1/a)) + 1, and T(b) = 1. Then T(n) is" (a) Theta(log_a log_b n) (b) Theta(log_ab n) (c) Theta(log_b log_a n) (d) Theta(log_2 log_2 n).

Answer: (a) Theta(log_a log_b n). After k steps, the input is n^(1/a^k). It reaches b when n^(1/a^k) = b, or a^k = log_b n. Therefore k = log_a log_b n. Open Q7 in the solved question bank.

Q8. GATE 2024

"Consider the following recurrence relation: T(n) = sqrt(n) * T(sqrt(n)) + n for n >= 1, T(1) = 1 for n = 1. Which one of the following options is CORRECT?" (a) T(n) = Theta(n log log n) (b) T(n) = Theta(n log n) (c) T(n) = Theta(n^2 log n) (d) T(n) = Theta(n^2 log log n).

Answer: (a) Theta(n log log n). Divide by n and set S(n) = T(n)/n. This gives S(n) = S(sqrt(n)) + 1, which Q6 shows is Theta(log log n). Hence T(n) = Theta(n log log n). Q3 divided by 2^n; Q8 divides by n. Normalising is half the method. Open Q8 in the solved question bank.

Reading the recurrence out of code (Q9-Q11)

First count the recursive calls and the work outside them. Then solve.

Q9. ISRO 2015

"The time complexity of the following C function is (assume n > 0)"

int recursive (int n) {
     if(n == 1)
     return (1);
     else
     return (recursive (n-1) + recursive (n-1));
}

(a) O(n) (b) O(n log n) (c) O(n^2) (d) O(2^n).

Answer: (d) O(2^n). Two calls on n-1 give T(n) = 2T(n-1) + c. The factor 2 repeats for n-1 levels, producing exponential growth. One call would be linear. Open Q9 in the solved question bank.

Q10. GATE 2008

"Consider the following C program"

int f1(int n)
{
    if (n == 0 || n == 1)
        return n;
    else
        return (2 * f1(n - 1) + 3 * f1(n - 2));
}

int f2(int n)
{
    int i;
    int X[N], Y[N], Z[N];

    X[0] = Y[0] = Z[0] = 0;
    X[1] = 1; Y[1] = 2; Z[1] = 3;
    for (i = 2; i <= n; i++) {
        X[i] = Y[i - 1] + Z[i - 2];
        Y[i] = 2 * X[i];
        Z[i] = 3 * X[i];
    }
    return X[n];
}

"The running time of f1(n) and f2(n) are" (a) theta(n) and theta(n) (b) theta(2^n) and theta(n) (c) theta(n) and theta(2^n) (d) theta(2^n) and theta(2^n).

Answer: (b) theta(2^n) and theta(n). f1 branches into calls on n-1 and n-2 without memoisation, so the call tree grows exponentially. f2 computes the sequence bottom-up with one loop, so it is linear. This is the central recursion-versus-tabulation idea explained in Dynamic Programming Explained. Open Q10 in the solved question bank.

Q11. ISRO 2017

"The recurrence relation that arises in relation with the complexity of binary search is:" (a) T(n) = 2T(n/2) + k, where k is constant (b) T(n) = T(n/2) + k, where k is constant (c) T(n) = T(n/2) + log n (d) T(n) = T(n/2) + n.

Answer: (b). Binary search makes one call on half the array after constant work. Expanding T(n) = T(n/2) + k reaches the base after log n levels. Option (a) is merge-sort-shaped; option (d) is quickselect-shaped: linear partition work, then recurse into one half. Open Q11 in the solved question bank.

Capstone: match four recurrences to their bounds (Q12)

Q12. GATE 1999

"If T(1) = O(1), match the following recurrence relations with their asymptotic bounds: (M) T(n) = T(n - 1) + n; (N) T(n) = T(n/2) + n; (O) T(n) = T(n/2) + n log n; (P) T(n) = T(n - 1) + log n. Bounds: (U) T(n) = O(n); (V) T(n) = O(n log n); (W) T(n) = O(n^2); (X) T(n) = O(log^2 n)." (a) M-W, N-V, O-U, P-X (b) M-W, N-U, O-X, P-V (c) M-V, N-W, O-X, P-U (d) M-W, N-U, O-V, P-V.

Answer: (d) M-W, N-U, O-V, P-V.

• M sums 1 + 2 + ... + n, so it is O(n^2).

• N sums n + n/2 + n/4 + ..., which stays below 2n, so it is O(n).

• O sums n log n + (n/2) log(n/2) + ...; the decreasing geometric weights keep it O(n log n).

• P sums log 1 + log 2 + ... + log n = log(n!), so it is O(n log n).

Bound X is a decoy, and V is used twice. Open Q12 in the solved question bank.

How to practise this subtopic

Recurrence problems reduce to arithmetic series, geometric patterns, or root-counting arguments. Train recognition instead of memorising answers. KnowledgeGate's practice bank has about 45 Substitution Method questions, each with a full worked solution.

Practise them inside GATE Guidance by Sanchit Sir, then time yourself on mixed sets in the GATE Test Series, Mocks & Topic-wise Tests. For the next set, use the Algorithms MCQs category, then connect the recurrence patterns to Sorting Algorithms: Complexity, Stability, n log n Bound.

The short version: write the recurrence, expand two or three levels, identify the series, and test the answer at a small input when possible.