Archive for January 30th, 2011

  |  
January 30, 2011

For the Nth time

by Bobby Corpus

We are sometimes irritated when somebody does something stupid and repeatedly does so. That’s why we use the phrase “for the nth time” to describe the fact that you’ve already lost count of such things. So where does this phrase come from? I would probably think this came from mathematics and especially that technique called mathematical induction.

There are some statements in mathematics which we think to be true but we are not really sure of it. One class of these problems have something to do with statements about sequences of numbers. For example, if somebody told you that the sum the first n natural numbers is equal to \frac{n(n+1)}{2}, would you believe it? You can either derive this result or you can try it out for a few numbers to convince yourself that it is true. But if this statement is true for the first few numbers, there is no guarantee that it will be true for all numbers. To convince ourselves, we use the mathematical induction technique.

The mathematical induction is a two step process. If you wish to prove that f(n) is true for all positive integers n,

  1. Basis Step – First show that it is true for n = 1
  2. Inductive Step – Assume that f(n) is true. Prove that f(n+1) is true.

When you have shown both steps to be true, then you have shown that f(n) is true for all positive integer n.

An Example

Show that

\displaystyle f(n) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}

If we substitute n = 1 to the above expression, we get f(1) = \frac{1(1+1)}{2} = \frac{2}{2} = 1

We have just shown that the basis step is true. Now let’s work on the inductive step. Assuming that f(n) is true, we now show that it is also true for f(n+1). How do we do this? We can write f(n+1) as the sum of the first n terms and n+1, that is,

\displaystyle f(n+1) = \sum_{i=1}^{n+1} i = \frac{n(n+1)}{2} + (n+1)

Then we simplify the right hand side:

\displaystyle = \frac{n(n+1) + 2n + 2}{2}
\displaystyle = \frac{n^2 + n + 2n + 2}{2}
\displaystyle = \frac{n^2 + 3n + 2}{2}

Notice that we can factor the quadratic expression of the numerator:

\displaystyle = \frac{(n+1)(n+2)}{2}
\displaystyle = \frac{(n+1)(n + 1 + 1)}{2}
\displaystyle = \frac{(n+1)\Bigg[(n+1) + 1\Bigg]}{2}

Now the last expression is precisely what you will get when you substitute n+1 to f(n):

\displaystyle f(n) = \frac{n(n+1)}{2} \Rightarrow f(n+1) = \frac{(n+1) ( n+1 +1)}{2}

We have just shown, using the mathematical induction technique, that \sum_{i=1}^{n} i = \frac{n(n+1)}{2} is true for all positive integers. Using this technique, how would you show that the binary search algorithm has running time a_n = \lfloor \log_2 n \rfloor + 1?

Posted in Algorithms and Complexity | Leave a Comment »

Tags: , , , ,
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}).

Posted in Algorithms and Complexity | 1 Comment »

Tags: , , , , , ,
  |  
Follow

Get every new post delivered to your Inbox.