Question

Q. A sequence X1, X2, ... , Xn is said to be cyclically sorted if the smallest number in the sequence is Xi for some unknown ?, and the sequence Xi, Xi+1, Xn, ... , X1, X2,....Xi-1 is sorted in an increasing order. Design an algorithm to find the position of the minimal element in a cyclically sorted ? distinct elements. (6 points) If your algorithm uses recursion, you need so show the recurrence function. Otherwise, show a closed-end form of the running time function. (2 points) Show that your algorithm in ?(log ?) time. (2 points) (No need to prove the bound).

Answer 1

The cyclically sorted array has a minimal element in the whole list X₁,X₂, ....,X_n we can use binary search to do this. keep finding middle element and check if the element to it's left is greater than itself. This is the smallest element. Check if the first element is zero. Algorithm is as below using recursion

1. Take array, lower index and higher index as input to function and return index of smallest element

2. last element is left, if high == low return high

3. check if element doesn't exist if (high < low) return 0

4.   Find mid, mid = (low + high)/2

5. Check if element mid is minimum element.

6. if arr[mid] < arr[mid - 1] && mid > low , return mid second condition to be checked as mid-1 element can go out of bound for particular iteration

7. Check if we should proceed with left or right subarray. if element at position high is bigger than middle element cll function at step 1 for lower half else proceed with upper half

Recurrence function

T(n) = T(n/2) + c reducing by half plus constant time c

Time complexity

The problem cuts down to half of length passed to function everytime. this cuts down complexity by half every time.

T(n) = T(n/2) + c

T(n) = T(n/4) + c1 where c1 = c + another constant time

T(n) = T(n/8) + c2

This comes out to log n Hence the time complexity is O(log n)