Finding Recurrence Relation of a Search algorithm

Question

Suppose that we have a sorted array of integers $a[0],...,a[n]$ such that

$$a[i] \le a[j] \text{ for } 0 \le i \le j \le n$$

A student designs the following algorithm that searches for an occurrence of an integer b in the sequence $a[0],...,a[n]$:

boolean search(int[] a, first, last, int b)
{
   int middle = (first+last)/2;

   if (middle == first && a[middle]!=b) 
      return false;

   if (a[middle] == b) 
      return true;

   if (a[middle] < b)
      return search(a, middle, last, b);
   else
      return search(a, first, middle, b);
}

Develop a recurrence formula for the number of steps that need to be executed to complete the algorithm. For simplicity, we count all comparisons on lines 1 to 3 and the computation on line 0 as a single step.

My solution:

$$T(n) = T(n/2) + O(1)$$

I believe this algorithm is related to Binary Search Algorithm which is able to search for an element in a sorted list.

However, I am cheating here and not really trying to break-down the code in a way which helps me calculate a recurrence. Frankly am not sure where to being. Any help/hints are greatly appreciated.

score 1 · Accepted Answer · answered May 04 '15 at 07:46

Well, if you want to me more rigous about it, the first thing to do is to figure out what $n$ represents. It is the relevant length of the list, in the program that is

$$\newcommand{L}{\text{last}} \newcommand{F}{\text{first}} \newcommand{M}{\text{middle}} n \approx \L - \F$$

When you recur, you are only taking 1 of the 2 recursion cases. So your runtime is bounded above by whichever is greater. Or in short:

$$T(n) \le T( \text{max}(\L - \M, \M - \F) ) + c$$

So you need to establish that both $(\L - \M)$ and $(\M - \F)$ are less than or equal to $\frac{\L - \M}{2}$. To do that, use the statement that $\M = \left(\lfloor\frac{\L - \M}{2}\right\rfloor) $.

Really the above code isn't written very logically though, it is hard to see why it works. I'd suggest:

boolean search(int[] a, first, last, int b)
{
   // empty list contains nothing
   if (last < first) return false;

   int middle = (first+last)/2;

   // found
   if (a[middle] == b) return true;

   // too large
   if (a[middle] > b)  return search(a, first, middle - 1, b);

   // too small
   else                return search(a, middle + 1, last, b);

}

It is much easier to prove the correctness and ordinal decent of a program written this way. The $-1$ and $+1$ on the middle variable in the recurrence call makes the decreasing obvious.

Finding Recurrence Relation of a Search algorithm

1 Answers1