Algorithms and Data Structures · Senior · Question 23 of 75
By the master theorem, what is the complexity of T(n) = 2T(n/2) + O(n)?
- 1O(n) like a single loop
- 2O(n²) because of two calls
- ✓Correct answer: O(n log n)
Explanation
Two halves with linear work to combine is the merge sort recurrence. Each of the log n levels of recursion does O(n) work in total. T(n) = 2T(n/2) + O(1) would be O(n), and T(n) = T(n/2) + O(1) is binary search, O(log n).