The recurrence T(n) = T(n/2) + O(1) for binary search solves to
AO(n) by unrolling
BO(log n) by halving log₂ n times
CO(n log n) by master theorem
DO(n²) by quadratic blowup
Answer & Solution
Correct answer: B. O(log n) by halving log₂ n times
Each step halves n, so after k steps the size is n/2^k. Reaching size 1 needs k = log₂ n steps, each doing constant work. Total: O(log n). Master theorem case 2 gives the same answer (a = 1, b = 2, d = 0; a = b^d so result is O(n^0 log n) = O(log n)).
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