Design And Analysis Of Algorithms Chapter 3
ems into smaller subproblems of the same kind, their time complexity is naturally expressed as recurrences. For instance, merge sort’s time complexity T(n) satisfies the recurrence: T(n) = 2T(n/2) + O(n) Here, the problem of size n is divided into two subproblems of size n/2,