Lets assume that you are given an integer, y, and a sorted list of integers. Design and analyze a divide and conquer algorithm that counts the number of occurrences of y in the list. Example is as follows: Suppose that we y= 13 and the list is{45,66,13,5,13,89,77,99,13,56,13}. The algorithm should return 4.

Give the pseudocode of your algorithm and prove that it is correct. Also provide the recurrence relation for the running time for the algorithm and solve its recurrence relation.