Exercise 4        Name __________________        Score __/22
Document last modified: 

1. (3) Linear Search of an Unordered Array

   This is not the usual linear search. We are searching to determine if a given key is a member of the array A. Give the recurrence equation for linearSearch.

   Give the recurrence equation for linearSearch.

   int linearSearch(A, key, n) {    if ( A[n] == key ) return true;    if ( n == 1) return false;    return linearSearch( A, n-1, key); }

    

2. (9) Exercises 4.3-1 by Master Theorem. Give case used.
    
3. (10) Draw the recursion tree and verify a good asymptotic upper bound (i.e. O) for the following recurrence. You will need to use Substitution Subtlety.

    

   æ c                        if n = 1 T(n) = í            è 4T(ën/2û) + cn     if n > 1

    

4. (10) Draw the recursion tree to provide a closed-form Big-O guess for:

    

   æ 2                        if n = 1 T(n) = í            è 9T(n/3) + dn       if n > 1