28 Write a recursive C implementation of the sequential sear

(28%) Write a recursive C++ implementation of the sequential search algorithm. The function takes as arguments an array, two indices start and stop and an element e. The function returns the index of the first occurrence of e in the range [start, stop). (Submit your function on Moodle.) (24%) Show that the solution to Exercise 2.1.3 satisfies the three properties of a correct recursive algorithm. (24%) Consider the recurrence relation T (n) = T(n - 1)+b [log n] if n greaterthanorequalto 2 T(1) = a Find an asymptotic solution to this recurrence relation. That is, find a simple function f (n) such that T(n) is Theta (f(n)). Do this by \"writing out\" the recurrence relation. (24%) Use induction to prove the upper bound you obtained in the previous exercise. (Do only the upper bound.)

Solution

Question 1:

Please checkout the recursive function given below for sequential search.

    if (start == stop) /* Initial condition to check whether only one element is in the array and that element is e or not */

{

if (array[start]=e){ // If the element is found in the middle of the search

cout<<\"Your search element is at \"<<start;

}

else

return false;

}

cout<<\"Your search element is at \"<<start; // This will return the index of the e, if found

int sequentialSearch(int array[], int start, int stop, int e)