PROBLEM 5 analysis (30 points) Solving the duplicates problem via divide and conquer Recall the has_dups problem: given an array, determine if there are any duplicates in the array and return true if there are and false otherwise (in which case all elements are distinct) On the next page is a divide-and-conquer approach to the problem. The idea is simple: . Recursively determine if the left half has any duplicates Recursively determine if the right half has any duplicates If neither half has duplicates, there may still be a duplicateone copy on the left and one on the right. o determine if this is the case by looping through the candidate pairs (one from left; one from right) Your Job: (A) Write a recurrence relation for the runtime of this algorithm Explain each component of the recurrence relation. (B) Use the recursion tree method (as we did with MergeSort) to derive a tight (big-Theta) bound on the worst-case runtime of the algorithm (C) Discuss: how does this approach compare with the simple approach you know from Homework 1