Recursion Tree Method MCQs: 12 Solved Questions with Explanations

A recursion tree exposes the non-recursive work contributed at each depth. It is especially useful when the standard Master Theorem does not fit, such as uneven splits, square-root arguments, or subtract-and-conquer recurrences. The reliable routine is to identify the cost of one node, multiply by the number of nodes at that depth, determine the stopping depth, and sum the level costs. Review the Algorithms learn module if the underlying recurrence notation needs a refresh. It also supplies the fallback theory for Q11 and Q12, which have no question-specific pages.

Recursion tree basics: add the work level by level

A recursion tree records the non-recursive work at every call. Add those costs level by level. Divide, conquer, and combine form its skeleton. The earlier Time Complexity MCQs collection uses the Towers of Hanoi question to identify a recurrence among mixed complexity problems; Q3 here uses that same bank question to construct and sum its exponential call tree.

Q1. BPSC PGT Tier-3 2024

Which of the following is NOT a step in the Divide and Conquer algorithm?

(a) Combine

(b) Conquer

(c) Divide

(d) More than one of the above

(e) None of the above

Answer: (e). Divide creates subproblems, conquer solves them, and combine joins their answers. All three belong, so none is a step that does not belong. Option (e) is part of the exam's five-option format.

Two calls on n - 1: the exponential recursion tree

Two calls on n - 1 double the nodes at every level. Level i has 2^i nodes and the depth is n - 1, giving 1 + 2 + ... + 2^(n-1) = 2^n - 1 nodes.

Q2. UPLT 2026

What is the time complexity of the following C function? (Assume n > 0)

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

(a) O(n²)

(b) O(2ⁿ)

(c) O(n log n)

(d) O(n)

Answer: (b). The recurrence is T(n) = 2T(n - 1) + O(1). Constant work at 2^i nodes per level sums to 2^n - 1, hence O(2^n). The linear option ignores the expanding call tree.

Q3. GATE 2012

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

(a) T(n) = 2T(n − 2) + 2

(b) T(n) = 2T(n − 1) + n

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

(d) T(n) = 2T(n − 1) + 1

Answer: (d). Move n - 1 discs aside, move the largest disc once, then move the n - 1 discs back. Thus T(n) = 2T(n - 1) + 1 = 2^n - 1 moves, the same exponential tree as Q2.

One branch with constant work: logarithmic answers

One constant-fraction child per call makes the tree a chain. For ratio 2/3, (2/3)^k n = 1 gives k = log_(3/2) n = Θ(log n).

Q4. UGC NET January 2025 Paper 2

Which of the following is the solution of T(n) = T(2n/3) + 1?

(a) Θ(n²)

(b) Θ(log n)

(c) Θ(n log n)

(d) Θ(n^(3/2))

Answer: (b). After k levels, the remaining problem size is (2/3)^k n. Reaching size 1 takes log_(3/2) n levels, and every level contributes 1, so T(n) = Θ(log n).

Q5. UGC NET December 2018 Paper 2

The solution of the recurrence relation T(m) = T(3m/4) + 1 is

(a) Θ(lg m)

(b) Θ(m)

(c) Θ(m lg m)

(d) Θ(lg lg m)

Answer: (a). The chain has depth log_(4/3) m and constant work per level, so its total is Θ(lg m). Double logarithms arise from repeated square roots, not fixed-fraction shrinkage.

Uneven splits: where the Master Theorem cannot help

For T(n) = T(an) + T(bn) + cn with a + b < 1, level work decays geometrically. The root then dominates and the total is linear.

Q6. GATE 2021 Set 1

Consider the following recurrence relation:

T(n) = T(n/2) + T(2n/5) + 7n if n > 0; 1 if n = 0.

Which one of the following options is correct?

(a) T(n) = Θ(n^(5/2))

(b) T(n) = Θ(n log n)

(c) T(n) = Θ(n)

(d) T(n) = Θ((log n)^(5/2))

Answer: (c). The root costs 7n. Level 1 costs 7(n/2) + 7(2n/5) = 7n(0.9) = 6.3n; level 2 costs 6.3n(0.9) = 5.67n. Thus level k costs 7n(0.9)^k, and the sum is 7n/(1 - 0.9) = 70n = Θ(n). The unequal fractions block the standard Master Theorem, but the level sums are decisive.

Q7. UGC NET December 2015 Paper 2

The solution of the recurrence relation is

T(n) ≤ θ(1) if n ≤ 80; T(n/s) + T(7n/10 + 6) + O(n) if n > 80.

(a) O(lg n)

(b) O(n)

(c) O(n lg n)

(d) None of the above

Answer: (d). Since s is missing, 1/s + 7/10 is unknown. For s > 10/3 it is below 1 and gives Θ(n); at s = 10/3 it gives Θ(n log n); smaller values make levels grow. No single bound follows, although median-of-medians uses s = 5 and is linear.

Harmonic level sums: the n lg lg n result

This is the hardest question in the set. Its shrinking logarithmic denominator produces a harmonic series across the levels.

Q8. UGC NET January 2017 Paper 2

The asymptotic upper bound solution of the recurrence relation T(n) = 2T(n/2) + n/lg n is

(a) O(n²)

(b) O(n lg n)

(c) O(n lg lg n)

(d) O(lg lg n)

Answer: (c). Level j has 2^j problems of size n/2^j, so its work is 2^j[(n/2^j)/lg(n/2^j)] = n/(lg n - j). Summing gives n(1/lg n + ... + 1) = nH_(lg n) = Θ(n lg lg n), hence option (c).

Square-root recurrences: change the variable first

For square-root arguments, set n = 2^k and S(k) = T(2^k). The earlier Master Theorem MCQs treats T(n) = 2T(√n) + 1 as a form that needs a variable change. Q9 instead counts its recursion-tree depth and branching, while Q10 changes the toll to log n.

Q9. GATE 2017 Set 2

Consider the recurrence function:

T(n) = 2T(√n) + 1 if n > 2; 2 if 0 < n ≤ 2.

Then T(n) in terms of Θ notation is

(a) Θ(log log n)

(b) Θ(log n)

(c) Θ(√n)

(d) Θ(n)

Answer: (b). If L square-root steps reach the base, n^(1/2^L) ≤ 2, so 2^L ≥ log₂ n and L = Θ(log log n). Level i has 2^i nodes, making the total Θ(2^L) = Θ(log n). Option (a) counts levels but misses the doubling calls.

Q10. UGC NET 2018

The solution of the recurrence relation T(n) = 2T(√n) + log n is

(a) O(log n log(log n))

(b) O(log n log n)

(c) O(n log n)

(d) O(log(n))

Answer: (a). Setting n = 2^k gives S(k) = 2S(k/2) + k = Θ(k log k). Back-substitution yields Θ(log n log log n). Unlike Q9's constant toll, the log n toll supplies the extra factor.

Exact recurrence forms and growth comparisons

The recurrences involve exact closed forms, while the growth comparisons use four separate bounds.

Q11. Concept question

Solve the recurrence relation: T(1) = 1, T(n) = 3T(n/2) + n.

(a) 3n + log₂(n) − 3^(log_(3/2) n)

(b) 2n + 3·log₂(n) − 3^(log_(3/2) n)

(c) 3^(log₂ n) − 2n + 2·n·(3/2)^(log₂ n)

(d) (3/2)^(log₂ n) + 2n + 2·n·(3/2)^(log₂ n)

Answer: (c). Set n = 2^k. Then S(k) = 3S(k - 1) + 2^k; its homogeneous part is C3^k, its particular solution is -2·2^k, and the base case gives T(n) = 3·3^(log₂ n) - 2n. Option (c) matches because n(3/2)^(log₂ n) = 3^(log₂ n); also, T(2) = 9 - 4 = 5 and T(4) = 27 - 8 = 19. Its asymptotic class is Θ(n^(log₂ 3)), but the exact form is required.

Q12. Concept question

Which of the following statements is/are TRUE?

I. The time complexity of recurrence relation T(n) = 2048T(n/2) + O(n^1000) has an asymptotically larger growth rate than T(n) = 4T(n - 1024) + O(1), T(0) = 1.

II. The time complexity of recurrence relation T(n) = 8T(n/2) + O(1) has an asymptotically larger growth rate than T(n) = 4T(n/8) + O(1).

(a) Only I

(b) Only II

(c) Both I and II

(d) None of the above

Answer: (b). Compare the growth rates directly. In I, log₂ 2048 = 11, so n^1000 dominates and gives Θ(n^1000), while 4^(n/1024) = 2^(n/512) is exponential, making I false. For II, the bounds are Θ(n^(log₂ 8)) = Θ(n³) and Θ(n^(log₈ 4)) = Θ(n^(2/3)). Since n³ grows faster, II is true.

The short version and your next step

• Draw the tree and sum the non-recursive work level by level.

• A single constant-fraction branch with constant work gives Θ(log n).

• Uneven split fractions whose sum is below 1 produce a root-dominated Θ(n) total when each node's work is linear.

• A shrinking logarithm in the denominator can turn level sums into a harmonic series and produce Θ(n log log n).

• For square-root arguments, substitute n = 2^k; count both the log log n levels and the branching inside them.

Continue with GATE Guidance by Sanchit Sir for the full Algorithms sequence. For a broader route across subjects and test practice, use the GATE CS Exam Preparation catalogue.