1) Write out the algorithm (pseudocode) to find K in the ordered array by the me

Question

1) Write out the algorithm (pseudocode) to find K in the ordered array by the method that compares K to every fourth entry until K itself or an entry larger than K is found, and then, in the latter case, searches for K among the preceding three. How many comparisons does your algorithm do in the worst case?

2) Answer questions (a) and (b) below:

(a)    How many times exactly is the code block below executed?

For (i = 1, n)

{

                        For (j = 1, i)

{

For (k = 1, j)

{

code block

}

}

}

Hint: You have to start with n=1, then make assumption what you make expect for any given n = N, and check if the formula you found works for n =N+1. This is what we call prove by induction.

(b) What is the theta value of this code segment?

Explanation / Answer

1)

Algorithm to find k:

find(A[],n,k)//A array to search for k, n is size of array
{
   for(i=0;i<n;i=i+4)//increament by 4, to access every fourth element
   {
       if(A[i]<=k)//if current element is less or equal to k
       {
           break;//breaks at value i
       }

}
  
int c=4;//checking previous four numbers
while(c>0)
{
   c--;
   if(A[i]==k)return i;//returning postion
   i--;          
}
if(c==0)//means not found
return -1;
  
//in worst case it will make (n/4)+4 comparisions.
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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