1. Implement the merge-sort algorithm

a. Determine the correct basic operation

2. Test your algorithm on inputs of size 2^10, 2^11 ... 2^20.

If this is too slow then just run it on any set of powers of two.

3. Show the running time of each of these inputs

Choose a basic operation

Count the total number times that this basic operation is done for each

power of 2.

Display this count in a table

5. [12%] Give the time complexity for the following algorithm using two different approaches. You need to identify the basic operation first. F(int n) { If (n > 1) Return 2*F (n-1) ; Else Return 1; 1) [2%] What is the basic operation? 2) [2%]Set up the recurrence. Let T(n) be the # of basic operations. T(n) = 3) [4%] Use backward substitution to solve the recurrence and indicate the time complexity. 4) [4%] Write an iterative algorithm to solve the same problem.ALGORITHM S(n) //Input: A positive integer n //Output: The sum of the first n cubes if n = 1 return 1 else return S(n - 1) + n * n * n A. What does this algorithm compute? B. What is its basic operation? C. Does the number of times of the basic operation executed depend on the nature of the inputs of the same size? D. Set up a recurrence relation for the number of times the algorithm's basic operation is executed