7. Write a divide-and-conquer algorithm to find the number of rotations in a circularly sorted array of integers. Assume that there will never be duplicates in the array and that all rotations are done in the rightward direction. (Online sources don't seem consistent on what a clockwise vs anticlockwise rotation of an array/list is, so I use "rightward" here to avoid such nonsense.) Your algorithm must run in e(Ign) time in the worst case. Give the recurrence of your algorithm, and use the master method to show that the runtime is indeed as required. You may assume n, the length of the array, is known or can be determined in constant time. Here are examples of circularly sorted arrays: A 8, 9, 10, 2, 5, 6] has been rotated 3 times. A = 2,5,6,8,9,10) has been rotated 0 times . A = 20, 30, 40, 10) has been rotated 3 times, not 1 time. A= 31, 35, 37, 39, 40, 8, 15, 20, 23) has been rotated 5 times. A (15, 20, 23, 31, 35, 37, 39, 40, 8) has been rotated 8 times. Hint: Assuming zero-based indexing, what index is the minimum element at in each of the above examples? Hint: As hinted at lw the e(lyn) worst case runtime requirement, your approach cannot "look at all elements of the array. You should be reducing your consideration to smaller and smaller halves of the array (similar to binary search). In one of your base cases, you should in O(1) time) check if the remaining subarray is already sorted