please please help me! god will bless you!! Both of this questions are related b

Question

please please help me! god will bless you!!

Both of this questions are related but one is providing the whole program and other is the theoretical analysis of the first program. Basically, these questions are from the analysis of algorithm area. pls, provide me both the answers and as accurate as possible.

1). Program problem:: Search: Find the index, k of an element x in the array S of n elements, n < 1001, S[1..n]. If x is not in S, then return -1. For this Implement the sequential search and the binary search algorithms in the C++ language and also conduct the average case analysis for an ordered array for both the algorithm in the program implementation. For your experiment for time complexity, count the number of comparison operations in your program. And also provide the output if possible.

2). Theoretical analysis of program: Algorithm description (problem, inputs, outputs, pseudo-code) and theoretical average case analysis for the two algorithms according to the program.

Explanation / Answer

sequential search-

int sequential_search(int S[], int n, int x)

{

    int k;

int c=0; // c for calculating no. of calculations

    for (k= 0; k < n; k++)

{ c++;

if (S[k] == x)

cout<<"no. of comparisons "<<c;

return k;

}

    return -1;

}

so in sequential search we have to comapre the key with every element of the array if matched then return comparison c and index k.

so running time is order of O(n).

2. binary search-

in the start l=0 and r=n-1 and c=0 means no. of comparisons at start

means lower and higher index of searching array.

in this index of element k is mid when found.

int binary_search(int S[], int l, int r, int x,int c )

{

   if (r >= l)

   { c+=1; //increase comparison no. beacuse comaprison needed.

        int mid = l + (r - l)/2;

        if (S[mid] == x)    // If the element is present at the middle itself then return

            return mid;

        // If element is smaller than mid, then it can only be present in left subarray

if (S[mid] > x)

            return binary_search(S, l, mid-1, x); // go for left array search

        // Else the element can only be present in right subarray

        return binary_search(S, mid+1, r, x); //go for right array search

   }  

   return -1;

}

so in this algo no. of comparison done only for the mid element of searching array with l and r so.

no. of comparisons is in order of log base 2 so running complexity is O(log2 (n) ).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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