Consider an ordered array A. of size n and the following ternary search algorith
ID: 3563985 • Letter: C
Question
Consider an ordered array A. of size n and the following ternary search algorithm for finding the index i such that A[i]=K. Divide the array into three parts. If A[n/3] > K, the first third of the array is searched recursively, else if A[2n/3] > then the middle part of the array is searched recursively, else the last third of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3] = K, or return 2n/ 3if A[2n/3]=K. (a) Write the recurrence relation for the number of comparisons C(n) in the worst case for the ternary, search and solve it.Explanation / Answer
We now consider a slightly modified take on ternary search in which only one
comparison is made which creates two partitions, one of roughly n/3 elements
and the other of 2n/3. Here the worst case arises when the recursive call is on
the larger 2n=3-element partition. Thus the recurrence corresponding to this
worst case number of comparisons is
T(n) = T(2n/3) + 1
By Master theorem, the number of comparisons come out to be O(logn).