Question

The recurrence T(n) = 2T(n/2) + n has a solution of _______.

• A. O(n)
• B. O(nlogn)
• C. O(n²)
• D. O(logn)

Hint:

For divide and conquer recurrences, master theorem can be used to determine the complexity quickly.

Answer 1

The Correct Option is B

The given recurrence is a divide and conquer recurrence, and it can be solved using the master theorem. The solution to this recurrence is O(nlogn), as it fits the second case of the master theorem.