In a previous post, we derived an expression for the running time of the binary search using a recurrence relation. We also solved this recurrence relation using the brute force method. In this article, we are going to derive a general expression for the running time of the divide and conquer algorithm.

A divide and conquer algorithm has a recurrence relation in the form

where is an increasing function. Looking at this recurrence relation, the right hand side says that the total executions for an input of size is equal to the number of executions of a sub-problem of size times some number plus some function of . The recurrence relation of the binary search algorithm, which is one type of divide and conquer algorithm, is . In this case, and .

As usual, we make things simpler by assuming that , for some integer . We can expand the recurrence relation above using the first few terms:

Plugging these results back to the expression for , we get

Substituting the expression for we get

And one more time for ,

We are starting to see a pattern here! If we continue this k number of times, we should get

The reason why we have is because .

Let us simplify a bit and assume that , where c is a constant. In this case, the above expression will simplify to

**Case when a = 1**

When , the second term of the above expression is just . Therefore,

Since , then by definition of logarithms, we have

In the realistic case where is not a power of b, then we can find between powers of , that is,

for some . Taking the logarithms of the above expression, we get

Since is an increasing function, substituting to , we get

Therefore, when , the function is .

**Case when a > 1**

Let’s digress for a while and review the definition of logarithms. Let a, b, and c be positive real numbers, if , then the logarithm of a to the base b is

From this definition, we therefore have the identity . We can further show that

To see this, let

Taking the logarithms, we get

Raising both sides to the power , we get

Therefore,

Having taken cared of that, let’s now return to the case where . Let’s write again our expression for ,

For , the right term of the above expression is just a geometric progression whose sum is

Plugging this into our expression for f(n), we get

If we assume , we have and . Therefore,

where and .

Now, what happens when n is not a power of b? As usual, we have and

Therefore, for , f(n) is .

## One thought on “Conquering Divide and Conquer”