3. Mergesort algorithm is an efficient sorting algorithm bases on divide-and-conquer strategy. This algorithm sorts n elements, where n > 1, as follows: Divide the array into two halves. (If n is even, then each half has exactly n/2 elements. Other- wise, the two halves are of size [n/2] and [n/2].) Sort each half recursively. Merge the two sorted halves. Let f(n) be the worst-case number of key-comparisons for mergesort algorithm to sort n elements. Assume the special case when n is a power of 2. (That is, n = 2k for some integer k.) The following recurrence holds for this special case. f(n) = { 2f (n/2) + n - 1, n > 1 0, = 1. (2) n = Prove by induction the solution has the following upper bound. (Note: All logorithms in this course are assumed to be in base 2, unless stated otherwise.) f(n)