Analysis of Algorithm course

Please print or write neatly

3. Recurrence (15 points) An algorithm processes an array of size n by operating on its first one-third, its second one-third, its third one-third, and then operating on its third one-third again, recursively. It then combines the solutions in 21gn time. Derive a recurrence for the running time of above algorithm. You may assume that n=3k for some positive integer k. Use an appropriate method (just pick one method) to solve the recurrence by finding a tight upper and lower bound solution for the recurrence. You must show the procedure of calculation. 4. Use substitution method to prove the correctness of your answer to problem 3 above. Be sure to justify both the 0 and 12 parts of the notation. (15 points)