alleryStart learning →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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.