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.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for