The recurrence T(n) = 2T(n/2) + 2 with T(1) = c solves by iteration to
AO(log n)
BO(n log n)
CO(n)
DO(n²)
Answer & Solution
Correct answer: C. O(n)
Unrolling k = log₂ n levels: T(n) = 2^k · T(1) + 2(2^k - 1). With 2^k = n, this is O(n). The min-max divide-and-conquer algorithm hits exactly this recurrence; the work doubles at each level but the per-level constant is small, so the dominant term is the bottom recursion which is O(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