Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Running Time of Divide-and-Conquer Algorithms

A number of divide-and-conquer algorithms are presented in the preceding sections. Because these algorithms have a similar form, the recurrences which give the running times of the algorithms are also similar in form. Table gif summarizes the running times of Programs gif, gif and gif.

 

 

program recurrence solution
Program gif T(n)=T(n/2)+O(1) tex2html_wrap_inline59891
Program gif T(n)=2T(n/2)+O(1) O(n)
Program gif T(n)=2T(n/2)+O(n) tex2html_wrap_inline59897
Table: Running Times of Divide-and-Conquer Algorithms

In this section we develop a general recurrence that characterizes the running times of many divide-and-conquer algorithms. Consider the form of a divide-and-conquer algorithm to solve a given problem. Let n be a measure of the size of the problem. Since the divide-and-conquer paradigm is essentially recursive, there must be a base case. I.e., there must be some value of n, say tex2html_wrap_inline59043, for which the solution to the problem is computed directly. We assume that the worst-case running time for the base case is bounded by a constant.

To solve an arbitrarily large problem using divide-and-conquer, the problem is divided into a number smaller problems, each of which is solved independently. Let a be the number of smaller problems to be solved ( tex2html_wrap_inline68785, tex2html_wrap_inline68787). The size of each of these problems is some fraction of the original problem, typically either tex2html_wrap_inline68789 or tex2html_wrap_inline68791 ( tex2html_wrap_inline68793, tex2html_wrap_inline68795).

The solution to the original problem is constructed from the solutions to the smaller problems. The running time required to do this depends on the problem to be solved. In this section we consider polynomial running times. I.e., tex2html_wrap_inline60893 for some integer tex2html_wrap_inline61524.

For the assumptions stated above, the running time of a divide-and-conquer algorithm is given by

  equation33009

In order to make it easier to find the solution to Equation gif, we drop the tex2html_wrap_inline58163s as well as the tex2html_wrap_inline58485 from the recurrence. We can also assume (without loss of generality) that tex2html_wrap_inline59539. As a result, the recurrence becomes

displaymath68763

Finally, we assume that n is a power of b. I.e., tex2html_wrap_inline68811 for some integer tex2html_wrap_inline68813. Consequently, the recurrence formula becomes

  equation33017

We solve Equation gif as follows. Divide both sizes of the recurrence by tex2html_wrap_inline68815 and then telescope :

   eqnarray33027

Adding Equation gif through Equation gif, substituting T(1)=1 and multiplying both sides by tex2html_wrap_inline68815 gives

  equation33058

In order to evaluate the summation in Equation gif we must consider three cases:




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.