Final answer:
The recurrence relation T(n) = 2T(n/2) + cn is associated with the merge sort algorithm. Using the iteration method and recursion-tree method for this recurrence both yield an upper bound of O(n log n) for the time complexity of merge sort.
Step-by-step explanation:
The recurrence relation T(n) = 2T(n/2) + cn is commonly associated with the merge sort algorithm. This is because merge sort recursively divides the array into two halves, sorts each half, and then merges the sorted halves, which reflects the recursive structure and the cn term for the merging process.
To apply the iteration method for an upper bound on T(n), we can expand the recurrence as follows:
- T(n) = 2T(n/2) + cn
- T(n/2) = 2T(n/4) + c(n/2)
- T(n/4) = 2T(n/8) + c(n/4)
- ...
- T(1) = 2T(1/2) + c
After k iterations, we reach the base case T(1) when n = 2^k. The sum of the costs cn, c(n/2), c(n/4), ..., c forms a geometric series with a sum of O(n log n), resulting in an upper bound of O(n log n) for T(n).
Using the recursion-tree method, we construct a binary tree where each non-leaf node has a cost of cn and each of the n/2^k leaf nodes at level k has a cost T(1). The total cost at each level is cn, and since there are log n levels, the total cost is O(n log n), reconfirming the upper bound found using the iteration method.