Iteratively unrolling T(n) = T(n/2) + c, the total work after reaching T(1) is
AT(1) + c·log₂ n, giving O(log n)
BT(1) + c·n, giving O(n)
CT(1) · 2^n, exponential growth
DT(1) · n^2, quadratic growth
Answer & Solution
Correct answer: A. T(1) + c·log₂ n, giving O(log n)
Each level halves n, contributing constant c work. To go from n down to 1, you need log₂ n halvings. Total: T(n) = T(1) + c · log₂ n = O(log n). This is binary search's running time, and it pops out cleanly from iteration without needing the master theorem.
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