goldschd@strose.edu

 Be sure to email me HOMEWORK 1 and LAB 2
   by 11:59pm today (Tuesday 5/26)

------------------------------------------

 ASSUME: n is non-negative

           -
          /  0                 if n == 0
         /
 f(n) = <    1                 if n == 1
         \
          \  f(n-1) + f(n-2)   if n > 1
           -

 Write a recursive function and call it from
   main() with various values of n

--------------------------------------------------

  GIVEN: list of size n

 Linear Search: start at index 0 and compare to x.
     If not found, go to index 1, 2, 3, ....

   Best-case: O(1) -- first element is x

   Worst-case: O(n) -- last element is x
                        OR x is not in the list

   Average-case: n/2 ==> O(n) 

   Linear search is O(n)

 Binary Search:

   Best-case: O(1) -- middle element of x

   Average/Worst Case: O(log n)
                            2