# Algorithms problem 2

Here is the code again for reference.

01 function find_closest(input_array, target)}
02   sorted_array = cocktailsort(input_array)
03   return find_closest_sorted(sorted_array, target)

04 function find_closest_sorted(sorted_array, target)
05    length = get_length(sorted_array)    // takes constant time
06    if length = 0
07        return NULL
08    else if length = 1
09        if sorted_array[0] >= target
10               return sorted_array[0]
11        else return NULL
12    else
13        mid = floor(length/2)
14        if (sorted_array[mid-1] < target)
15           half_array = sorted_array(mid,...,length-1)     // array containing second half of elements
16        else
17           half_array = sorted_array(0, ...,mid-1)         // array containing first half of elements
18         return find_closest_sorted(half_array, target)


Also remember that cocktailsort was described as taking $$\Theta(n^2)$$ time.

### Solution

(a) Recursive definition for the running time of find_closest_sorted on an input of length n:

$$\begin{eqnarray*} R(0) &=& c \\ R(1) &=& d \\ R(n) &=& R(n/2) + p \end{eqnarray*}$$

(b) The recursion tree for R(n) has height $$\log n$$.

(c) The recursion tree for R(n) has one leaf.

(d) The big-Theta running time of find_closest_sorted is $$\Theta(\log n)$$.

(e) Notice that the first step in find_closest is to call cocktailsort on the input array. Cocktailsort takes $$\Theta(n^2)$$ time, so the big-Theta running time of find_closest is $$\Theta(n^2)$$.

### Comments

You aren't expected to have any idea how cocktailsort works or why it takes $$\Theta(n^2)$$. That's a separate project. Clearly it's not the world's best implementation of sorting, since mergesort only takes $$\Theta(n\log n)$$ time. This problem is just about using that information to figure out how fast find_closest is.

### Self-check

The three constants c, d, p should be different. (Though it's a common place for reasonable people to get sloppy.) You could also write the recursive definition using O(1):

$$\begin{eqnarray*} R(0) &=& O(1) \\ R(1) &=& O(1) \\ R(n) &=& R(n/2) + O(1) \end{eqnarray*}$$

The case of n=0 is a bit odd. You can't actually get to n=0 from the recursive calls, so the leaf level of the recursion tree is n=1. The n=0 case only runs when the original input had zero length. So it's really an initial error check rather than part of the recursive structure.