January 30, 2011

## Conquering Divide and Conquer

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

$\displaystyle f(n) = af(n/b) + g(n)$

where $f(n)$ is an increasing function. Looking at this recurrence relation, the right hand side says that the total executions for an input of size $n$ is equal to the number of executions of a sub-problem of size $n/b$ times some number $a$ plus some function of $n$. The recurrence relation of the binary search algorithm, which is one type of divide and conquer algorithm, is $a_n = a_{\lfloor n/2 \rfloor} + 1$. In this case, $f(n/b) = a_{\lfloor n/2 \rfloor}$ and $g(n) = 1$.

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

$\displaystyle f(n/b) = af(n/b^2) + g(n/b)$
$\displaystyle f(n/b^2) = af(n/b^3) + g(n/b^2)$
$\displaystyle f(n/b^3) = af(n/b^4) + g(n/b^3)$

Plugging these results back to the expression for $f(n)$, we get

$\displaystyle f(n) = a \big[ a f(n/b^2) + g(n/b) \big] + g(n)$
$\displaystyle = a^2 f(n/b^2) + ag(n/b) + g(n)$

Substituting the expression for $f(n/b^2)$ we get

$\displaystyle f(n) = a^2 \big[ af(n/b^3) + g(n/b^2) \big] + ag(n/b) + g(n)$
$\displaystyle = a^3 f(n/b^3) + a^2g(n/b^2) + ag(n/b) + g(n)$

And one more time for $f(n/b^3)$,

$\displaystyle f(n) = a^3 \big[ af(n/b^4) + g(n/b^3) \big] + a^2g(n/b^2) + ag(n/b) + g(n)$
$\displaystyle = a^4 f(n/b^4) + a^3g(n/b^3) + a^2g(n/b^2) + ag(n/b) + g(n)$

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

$\displaystyle f(n) = a^k f(1) + \sum_{j=0}^{k-1} a^j g(n/b^j)$

The reason why we have $f(1)$ is because $n/b^k = 1$.

Let us simplify a bit and assume that $g(n) = c$, where c is a constant. In this case, the above expression will simplify to

$\displaystyle f(n) = a^k f(1) + c \sum_{j=0}^{k-1} a^j$

Case when a = 1

When $a = 1$, the second term of the above expression is just $\sum_{j=0}^{k-1} 1 = ck$. Therefore,

$\displaystyle f(n) = f(1) + ck$

Since $n = b^k$, then by definition of logarithms, we have

$\displaystyle f(n) = f(1) + c\cdot \log_b n$

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

$\displaystyle b^k < n < b^{k+1}$

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

$\displaystyle k < \log_b n < k + 1$

Since $f(n)$ is an increasing function, substituting $b^{k+1}$ to $f(n) = f(1) + ck$, we get

$f(n) < f(b^{k+1}) = f(1) + c(k+1) = \big[ f(1) + c \big] + ck \le \big[ f(1) + c \big] + c\cdot \log_b n$

Therefore, when $a = 1$, the function $f(n) = a^k f(1) + c \sum_{j=0}^{k-1} a^j$ is $O(\log_2 n)$.

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 $a = b^c$, then the logarithm of a to the base b is

$\displaystyle \log_b a = c$

From this definition, we therefore have the identity $a = b^{\log_b a}$. We can further show that

$a^{\log_b c} = c^{\log_b a}$

To see this, let

$\displaystyle y = a ^{\log_b c}$

Taking the logarithms, we get

$\displaystyle \log_a y = \log_b c$
$\displaystyle b^{\log_a y} = c$

Raising both sides to the power $\log_b a$, we get

$\displaystyle c^{\log_b a} = \big( b^{\log_b a}\big) ^{\cdot \log_a y}$
$\displaystyle = a^{\log_a y} = y = a ^{\log_b c}$

Therefore,

$\displaystyle a^{\log_b c} = c^{\log_b a}$

Having taken cared of that, let’s now return to the case where $a > 1$. Let’s write again our expression for $f(n)$,

$\displaystyle f(n) = a^k f(1) + c \sum_{j=0}^{k-1} a^j$

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

$\displaystyle \sum_{j=0}^{k-1} a^j = \frac{a^k - 1}{a-1}$

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

$\displaystyle f(n) = a^k f(1) + c \frac{a^k - 1}{a-1} = a^k f(1) + \frac{ca^k - c}{a-1}$
$\displaystyle = a^k\big[ f(1) + \frac{c}{a-1}\big] - \frac{c}{a-1}$

If we assume $n = b^k$, we have $\log_b n = k$ and $a^k = a^{\log_b n} = n ^{\log_b a}$. Therefore,

$\displaystyle f(n) = C_1 n^{\log_b a} + C_2$

where $C_1 = f(1) + c/(a-1)$ and $C_2 = - c/(a-1)$.

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

$\displaystyle f(n) \le f(b^{k+1}) = a^{k+1}\big[ f(1) + \frac{c}{a-1}\big] - \frac{c}{a-1}$
$\displaystyle = C_1 a^{k+1} + C_2$
$\displaystyle = (a\cdot C_1) \cdot a^k + C_2$
$\displaystyle = (a\cdot C_1) \cdot n ^{\log_b a} + C_2$

Therefore, for $a > 1$, f(n) is $O(n^{\log_b a})$.