Question

You are given T(n)=2T(n/2)+cn.

a) Which sorting algorithm's recurrence relation is T(n) ?
b) Apply the iteration method to arrive at an upper bound for the above T(n).
c) Apply the recursion-tree method to arrive at an upper bound for the above T(n).

5. Find the time complexity T(n) using Master Theorem: a) T(n)=9T(n/3)+n b) T(n)=3T(n/2)+n2

Answer 1

a) The recurrence relation T(n) = 2T(n/2) + cn corresponds to the Merge Sort algorithm. b) By applying the iteration method to the given recurrence relation, we find that the upper bound for T(n) is O(n log n). c) By applying the recursion-tree method, we find that the upper bound for T(n) is also O(n log n).

Step-by-step explanation:

a) The given recurrence relation is T(n) = 2T(n/2) + cn. This recurrence relation corresponds to the Merge Sort algorithm.

b) To apply the iteration method, we keep dividing n by 2 until we reach the base case T(1) = c. Then, we substitute these values back into the recurrence relation to find the upper bound. The upper bound for T(n) is O(n log n).

c) To apply the recursion-tree method, we draw a binary tree representing the recursive calls. Each level of the tree corresponds to a division of the input size by 2. The height of the tree is log n, and at each level, the total work done is cn. Summing up the work at each level, we find that the upper bound for T(n) is O(n log n).