One of the goals of these series of articles is to give a flavor of how we programmers get a feel of the running time of our algorithms. In the last article, we showed how fast a binary search is compared to a linear search using simple arguments that anyone can do. We do this routinely in elementary algebra where we get the solution of a quadratic equation and we try to see if we can reduce it to its common factors. However for general quadratic equations, we can always apply the quadratic formula to solve for the unknown. In this article, we are going to investigate solving for the running time of a binary search using a technique called recurrence relations.
We shall repeat below the listing of the binary search algorithm:
algorithm binarySearch( Array A): 1. get the middle element A[middle] 2. compare x with A[middle]. If x equals A[middle] return middle. 3. if x less than A[middle], return binary search(A[1:middle-1] 4. else return binarySearch(A[middle + 1, n])
Floor and Ceiling functions
In reality, we don’t always have arrays that come in lengths of powers of 2. So when we halve an array, it does not necessarily divide evenly. This means that we can get a number that is not an integer. To deal with situations like this, we define the floor and ceiling functions.
The floor function, when it operates on a real number , returns the largest whole number that is less than . On the other hand, the ceiling function, when it operates on an integer returns the smallest whole number that is greater than . We symbolize the floor function acting on a real number as and the ceiling function is denoted by . For example, if , then and . Now suppose, we have an array of length 10. If we halve this, we have 5. Halving again, we get 2.5, which is not an integer. So we either get the floor to get 2 or the ceiling to get 3.
Continuing with the Analysis
In the binary search algorithm defined above, we did not specify how to compute “mid”. For the sake of our discussion, let us take , where is the length of the input array of the algorithm.
We observe from the binary search algorithm above the following:
– if the length is an odd number, the array can be split into two equal parts which is equal to . If the length is even, then the length of the right subarray is and the right-hand side has length . Since we are interested in the worst-case complexity of this algorithm, we take as the input to the next iteration.
– Every iteration has one comparison and it is comparing the search number to the middle element.
– The total number of comparisons is therefore equal to 1 plus the number of comparisons for the subarray of size .
Mathematically, this means that if is the size of the array and is the number of comparisons executed by the binary search for an array of size , then
where is the number of comparisons needed to run the binary search for an array of elements. The equation above is what is called a recurrence relation for the algorithm. In this case, it is the recurrence relation for the binary search algorithm. In the special case that the array has only one element, we impose the condition that
because there is only one comparison involved.
A Brute Force Solution
One way to solve this recurrence relation is by listing the first few terms of this recurrence relation.
and so on…
We now start to see a pattern! Look at the lines with * in them. We have a * when
So for powers of 2, . Now what happens between powers of 2?
So for between powers of 2, that is, , we see that . Since this expression is also satisfied for equal to powers of 2, the solution of the recurrence relation is therefore
Now, are we sure that this is true for all ? That's another topic we will discuss in a future post.