Posts tagged ‘floor function’

January 30, 2011

Conquering Divide and Conquer

by Bobby Corpus

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 <b^{k+ 1} 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}).

Follow

Get every new post delivered to your Inbox.