Question

The following is the pseudocode of algorithm that searches a sorted array of n items by dividing it into three sub arrays of almost n/3 items (7pt). Hint: refer Mergesort algorithm)

Input: Sorted array of Keys(A) indexed from 1 to n.
Output: Location, the Location of K in array A (hint: return 0 if K is no in A)
index location3 (int A[1…n ], index L, index H)
{
index m1, m2;
if (L > H) return 0;
else
   {
m1 = L + (H – L)/3;   //one third
m2 = L + 2*(H – L)/3;   //two thirds

      }
}
a)   Complete the pseudocode of the above algorithm which is indicated by blank box
b)   Analyze the worst-case time complexity of your algorithm in(a), and show the results using the asymptotic notation (ϴ)

Answer 1

a. In the algorithm, m1 and m2 gives indices of one third and two-thirds of the algorithm. Since this is a recursive algorithm, at each step we make some comparisons and runs the function again for the particular part of array. More specifically, we need to check whether the element K is greater or less than m1. If it is less than m1, search in the first one third of elements. If it is greater than m1, check whether it is greater or less than m2. If it is less than m2, search between indices m1 and m2, else search above m2. The stopping criteria can be if the element K equals the element at H or L. Hence the pseudocode at the blank box will be:

if A[H] == K, return H

else if A[L] == K, return L

else{

if K<A[m1], index(A[1...n], 0, m1)

else if K<A[m2], index(A[1....n],m1,m2)

else index(A[1....n],m2, n)

}

b. At each step the search space length is divided by 3. Assuming the worst case scenario in which the element is found at the last possible step, the worst case time complexity is O(log₃n). Notice that the base of the log here is 3 and not 2.