The following algorithm takes as input a sorted array of integers A. left and ri

Question

The following algorithm takes as input a sorted array of integers A. left and right represent the left and right indicies of the array that is being searched. The parameter x represents an integer. The algorithm Search searches whether or not x is in the array A. If x is in the array, it returns the index of x. If x is not in the array, it returns -1. The function floor(a) returns the integer part of a. The initial call to Search is Search( A, 1, n, x ).

int Search(A,left,right,x) {

numelements = right - left + 1;

if (numelements < 20) {

for (i = 0; i < numelements; i++){

if (A[left + i] == x)

return (left + i); }

return (-1); }

else {

split = floor(numelements * 1/7) + left;

if (A[split] == x) return(split);

if (A[split] > x) return(Search(A,left,split-1,x));

if (A[split] < x) return(Search(A,split,right,x)); } }

1. What is the recurrence for the worst-case runtime of the above algorithm?

Explanation / Answer

lets say total number elements is n.

If the number elements are more then 20 (n>20), then it will split total elements into left+(n/7), that means one half is n/7 and the other half is 6n/7.

so if we consider the time complexity for inital Search(A,left,right,x) as T(n) then

Search(A,left,split-1,x) will take T(n/7) and

Search(A,split,right,x) will take T(6n/7).

and the recurrence break point is when (n<20).

So we conclude the time complexity is

if(n>20)

         T(n)=n/7 + 6n/7

if(n<20)

        T(n)=n

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.