A Recurring Theme

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 x, returns the largest whole number that is less than x. On the other hand, the ceiling function, when it operates on an integer x returns the smallest whole number that is greater than x. We symbolize the floor function acting on a real number x as \lfloor x \rfloor and the ceiling function is denoted by \lceil x\rceil. For example, if x = 3.14, then \lfloor x \rfloor = 3 and \lceil x \rceil = 4. 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 mid = \lfloor x/2 \rfloor, where x is the length of the input array of the algorithm.

We observe from the binary search algorithm above the following:

– if the length x is an odd number, the array can be split into two equal parts which is equal to \lfloor x \rfloor. If the length is even, then the length of the right subarray is \lfloor x/2 \rfloor -1 and the right-hand side has length \lfloor x/2 \rfloor. Since we are interested in the worst-case complexity of this algorithm, we take \lfloor x/2 \rfloor 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 \lfloor x/2 \rfloor.

Mathematically, this means that if n is the size of the array and a_n is the number of comparisons executed by the binary search for an array of size n, then

\displaystyle a_n = a_{\lfloor n/2 \rfloor} + 1

where a_{\lfloor n/2 \rfloor} is the number of comparisons needed to run the binary search for an array of \lfloor n/2 \rfloor 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

\displaystyle a_1 = 1

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.
\displaystyle a_1 =  1*
\displaystyle a_2 = a_{\lfloor 2/2 \rfloor} + 1 = a_{1} + 1 = 1 + 1 = 2*
\displaystyle a_3 = a_{\lfloor 3/2 \rfloor} + 1 = a_{1} + 1 = 1 + 1 = 2
\displaystyle a_4 = a_{\lfloor 4/2 \rfloor} + 1 = a_{2} + 1 = 2 + 1 = 3*
\displaystyle a_5 = a_{\lfloor 5/2 \rfloor} + 1 = a_{2} + 1 = 2 + 1 = 3
\displaystyle a_6 = a_{\lfloor 6/2 \rfloor} + 1 = a_{3} + 1 = 2 + 1 = 3
\displaystyle a_7 = a_{\lfloor 7/2 \rfloor} + 1 = a_{3} + 1 = 2 + 1 = 3
\displaystyle a_8 = a_{\lfloor 8/2 \rfloor} + 1 = a_{4} + 1 = 3 + 1 = 4*
\displaystyle a_9 = a_{\lfloor 9/2 \rfloor} + 1 = a_{4} + 1 = 3 + 1 = 4
\displaystyle a_{10} = a_{\lfloor 10/2 \rfloor} + 1 = a_{5} + 1 = 3 + 1 = 4
\displaystyle a_{11} = a_{\lfloor 11/2 \rfloor} + 1 = a_{5} + 1 = 3 + 1 = 4
\displaystyle a_{12} = a_{\lfloor 12/2 \rfloor} + 1 = a_{6} + 1 = 3 + 1 = 4
\displaystyle a_{13} = a_{\lfloor 13/2 \rfloor} + 1 = a_{6} + 1 = 3 + 1 = 4
\displaystyle a_{14} = a_{\lfloor 14/2 \rfloor} + 1 = a_{7} + 1 = 3 + 1 = 4
\displaystyle a_{15} = a_{\lfloor 15/2 \rfloor} + 1 = a_{7} + 1 = 3 + 1 = 4
\displaystyle a_{16} = a_{\lfloor 16/2 \rfloor} + 1 = a_{8} + 1 = 3 + 1 = 5*

and so on…

We now start to see a pattern! Look at the lines with * in them. We have a * when

\displaystyle n = 1 = 2^0, \text{ and } a_{n} = 1
\displaystyle n = 2 = 2^1, \text{ and } a_{2} = 2 = 1 + 1
\displaystyle n = 4 = 2^2, \text{ and } a_{n} = 3 = 2 + 1
\displaystyle n = 8 = 2^3, \text{ and } a_{n} = 4 = 3 + 1
\displaystyle n = 16 = 2^4, \text{ and } a_{n} = 5= 4 + 1

So for powers of 2, a_n = \log_2 n + 1. Now what happens between powers of 2?

\displaystyle n = 3, a_{3} = 1 + 1
\displaystyle n = 5, a_{5} = 2 + 1
\displaystyle n = 6, a_{5} = 2 + 1
\displaystyle n = 7, a_{5} = 2 + 1
\displaystyle n = 9, a_{5} = 5 + 1
\displaystyle n = 10, a_{5} = 5 + 1
\displaystyle n = 11, a_{5} = 5 + 1
\displaystyle n = 12, a_{5} = 5 + 1
\displaystyle n = 13, a_{5} = 5 + 1
\displaystyle n = 14, a_{5} = 5 + 1
\displaystyle n = 15, a_{5} = 5 + 1

So for n between powers of 2, that is, 2^n \le n < 2^{n+1}, we see that a_{n} = \lfloor \log_2 n \rfloor + 1. Since this expression is also satisfied for n equal to powers of 2, the solution of the recurrence relation is therefore

\displaystyle a_n = \lfloor \log_2 n \rfloor + 1

Now, are we sure that this is true for all n? That's another topic we will discuss in a future post.

Advertisements

Published by

Bobby Corpus

Loves anything related to Mathematics, Physics, Computing and Economics.

One thought on “A Recurring Theme”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s