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
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 .