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

Example-Computing Powers

In this section we consider the running time to raise a number to a given integer power. That is, given a value x and non-negative integer n, we wish to compute the tex2html_wrap_inline57963. A naıve way to calculate tex2html_wrap_inline57963 would be to use a loop such as

int result = 1;
for (int i = 0; i <= n; ++i)
    result *= x;
While this may be fine for small values of n, for large values of n the running time may become prohibitive. As an alternative, consider the following recursive definition

  equation1050

For example, using Equation gif, we would determine tex2html_wrap_inline57975 as follows

displaymath57951

which requires a total of five multiplication operations. Similarly, we would compute tex2html_wrap_inline57977 as follows

displaymath57952

which requires a total of eight multiplication operations.

A recursive algorithm to compute tex2html_wrap_inline57963 based on the direct implementation of Equation gif is given in Program gif. Table gif gives the running time, as predicted by the simplified model, for each of the executable statements in Program gif.

   program1068
Program: Program to compute tex2html_wrap_inline57963.

 

 

time

statement

n=0 n>0 n>0
n is even n is odd
5 3 3 3
6 2 -- --
7 -- 5 5
8 -- tex2html_wrap_inline58005 --
10 -- -- tex2html_wrap_inline58007
TOTAL 5 tex2html_wrap_inline58011 tex2html_wrap_inline58013
Table: Computing the running time of Program gif.

By summing the columns in Table gif we get the following recurrence for the running time of Program gif

  equation1091

As the first attempt at solving this recurrence, let us suppose that tex2html_wrap_inline58019 for some k>0. Clearly, since n is a power of two, it is even. Therefore, tex2html_wrap_inline58025.

For tex2html_wrap_inline58019, Equation gif gives

displaymath57953

This can be solved by repeated substitution:

eqnarray1101

The substitution stops when k=j. Thus,

eqnarray1107

Note that if tex2html_wrap_inline58019, then tex2html_wrap_inline58033. In this case, running time of Program gif is tex2html_wrap_inline58035.

The preceding result is, in fact, the best case--in all but the last two recursive calls of the method, n was even. Interestingly enough, there is a corresponding worst-case scenario. Suppose tex2html_wrap_inline58039 for some value of k>0. Clearly n is odd, since it is one less than tex2html_wrap_inline58045 which is a power of two and even. Now consider tex2html_wrap_inline58047:

eqnarray1110

Hence, tex2html_wrap_inline58047 is also odd!

For example, suppose n is 31 ( tex2html_wrap_inline58053). To compute tex2html_wrap_inline57977, Program gif calls itself recursively to compute tex2html_wrap_inline58057, tex2html_wrap_inline58059, tex2html_wrap_inline58061, tex2html_wrap_inline58063, and finally, tex2html_wrap_inline58065--all but the last of which are odd powers of x.

For tex2html_wrap_inline58039, Equation gif gives

displaymath57954

Solving this recurrence by repeated substitution we get

eqnarray1118

The substitution stops when k=j. Thus,

eqnarray1124

Note that if tex2html_wrap_inline58039, then tex2html_wrap_inline58075. In this case, running time of Program gif is tex2html_wrap_inline58077.

Consider now what happens for an arbitrary value of n. Table gif shows the recursive calls made by Program gif in computing tex2html_wrap_inline57963 for various values of n.

 

 

n tex2html_wrap_inline58087 powers computed recursively
1 1 tex2html_wrap_inline58089
2 2 tex2html_wrap_inline58091
3 2 tex2html_wrap_inline58093
4 3 tex2html_wrap_inline58095
5 3 tex2html_wrap_inline58097
6 3 tex2html_wrap_inline58099
7 3 tex2html_wrap_inline58101
8 4 tex2html_wrap_inline58103
Table: Recursive calls made in Program gif.

By inspection we determine that the number of recursive calls made in which the second argument is non-zero is tex2html_wrap_inline58087. Furthermore, depending on whether the argument is odd or even, each of these calls contributes either 18 or 20 cycles. The pattern emerging in Table gif suggests that, on average just as many of the recursive calls result in an even number as result in an odd one. The final call (zero argument) adds another 5 cycles. So, on average, we can expect the running time of Program gif to be

  equation1148


next up previous contents index

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