Practice free →
HomeGATE CSEcomputerscienceAlgorithms › In the iterative solution to T(n) = a·T(n/b) + Θ…

In the iterative solution to T(n) = a·T(n/b) + Θ(n^d), if a < b^d, the dominant work is at

Athe deepest (smallest sub-problem) level
Bthe middle level only
Cthe level boundary, fluctuating between top and bottom
Dthe topmost level (largest sub-problem)
Answer & Solution
Correct answer: D. the topmost level (largest sub-problem)
The work at level j is proportional to a^j · (n/b^j)^d = n^d · (a/b^d)^j. When a/b^d < 1, the ratio decreases with depth, so the topmost level (j = 0) contributes the most. Result: T(n) = Θ(n^d), matching master-theorem case 1. When a > b^d the deepest level dominates; when equal, all levels contribute equally.
Solve this in the app — GATE CSE practice & 24k+ MCQs →
Related questions