page54.html

Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and

This can be solved by repeated substitution:
<P> <IMG WIDTH=500 HEIGHT=124 ALIGN=BOTTOM ALT="eqnarray1085" SRC="img171.gif"  ><P>
The substitution stops when <I>k</I>=<I>j</I>.
Thus,
<P> <IMG WIDTH=500 HEIGHT=87 ALIGN=BOTTOM ALT="eqnarray1091" SRC="img172.gif"  ><P>
Note that if  <IMG WIDTH=45 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58245" SRC="img168.gif"  >, then  <IMG WIDTH=69 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline58259" SRC="img173.gif"  >.
In this case, running time of Program&nbsp;<A HREF="page54.html#progexampleh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
is  <IMG WIDTH=148 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58261" SRC="img174.gif"  >.
<P>
The preceding result is, in fact, the best case--in all
but the last two recursive calls of the method, <I>n</I> was even.
Interestingly enough, there is a corresponding worst-case scenario.
Suppose  <IMG WIDTH=73 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58265" SRC="img175.gif"  > for some value of <I>k</I><I>&gt;</I>0.
Clearly <I>n</I> is odd, since it is one less than  <IMG WIDTH=13 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58271" SRC="img176.gif"  >
which is a power of two and even.
Now consider  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58273" SRC="img177.gif"  >:
<P> <IMG WIDTH=500 HEIGHT=62 ALIGN=BOTTOM ALT="eqnarray1094" SRC="img178.gif"  ><P>
Hence,  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58273" SRC="img177.gif"  > is also odd!
<P>
For example, suppose <I>n</I> is 31 ( <IMG WIDTH=41 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58279" SRC="img179.gif"  >).
To compute  <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58203" SRC="img160.gif"  >, Program&nbsp;<A HREF="page54.html#progexampleh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> calls itself
recursively to compute  <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58283" SRC="img180.gif"  >,  <IMG WIDTH=16 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58285" SRC="img181.gif"  >,  <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58287" SRC="img182.gif"  >,  <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58289" SRC="img183.gif"  >, and finally,  <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58291" SRC="img184.gif"  >--all but the last of which are odd powers of <I>x</I>.
<P>
For  <IMG WIDTH=73 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58265" SRC="img175.gif"  >, Equation&nbsp;<A HREF="page54.html#eqnmodelpowtime"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives
<P> <IMG WIDTH=385 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath58180" SRC="img185.gif"  ><P>
Solving this recurrence by repeated substitution we get
<P> <IMG WIDTH=500 HEIGHT=124 ALIGN=BOTTOM ALT="eqnarray1102" SRC="img186.gif"  ><P>
The substitution stops when <I>k</I>=<I>j</I>.
Thus,
<P> <IMG WIDTH=500 HEIGHT=39 ALIGN=BOTTOM ALT="eqnarray1108" SRC="img187.gif"  ><P>
Note that if  <IMG WIDTH=73 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline58265" SRC="img175.gif"  >, then  <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58301" SRC="img188.gif"  >.
In this case, running time of Program&nbsp;<A HREF="page54.html#progexampleh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
is  <IMG WIDTH=177 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58303" SRC="img189.gif"  >.
<P>
Consider now what happens for an arbitrary value of <I>n</I>.
Table&nbsp;<A HREF="page54.html#tblcalls"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the recursive calls made by
Program&nbsp;<A HREF="page54.html#progexampleh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> in computing  <IMG WIDTH=17 HEIGHT=11 ALIGN=BOTTOM ALT="tex2html_wrap_inline58189" SRC="img156.gif"  > for various values of <I>n</I>.
<P>
<P><A NAME="1217">&#160;</A>
<P>
    <A NAME="tblcalls">&#160;</A>
    <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=LEFT>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
	    <I>n</I> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>  <IMG WIDTH=78 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58313" SRC="img190.gif"  > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> powers computed recursively </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>1 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 1 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=23 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58315" SRC="img191.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    2 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=38 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58317" SRC="img192.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    3 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 2 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=39 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58319" SRC="img193.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    4 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=53 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58321" SRC="img194.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    5 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=53 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58323" SRC="img195.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    6 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=53 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58325" SRC="img196.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    7 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 3 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=53 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58327" SRC="img197.gif"  > </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 
	    8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> 4 </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>  <IMG WIDTH=68 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline58329" SRC="img198.gif"  > </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Recursive calls made in Program&nbsp;<A HREF="page54.html#progexampleh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</CAPTION></TABLE>
</P></DIV><P>
<P>
By inspection we determine that the number of recursive calls made
in which the second argument is non-zero is  <IMG WIDTH=78 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58313" SRC="img190.gif"  >.
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&nbsp;<A HREF="page54.html#tblpowerc"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> 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&nbsp;<A HREF="page54.html#progexampleh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
to be
<P><A NAME="eqnmodelpower">&#160;</A> <IMG WIDTH=500 HEIGHT=16 ALIGN=BOTTOM ALT="equation1132" SRC="img199.gif"  ><P><HR><A NAME="tex2html1827" HREF="page55.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1825" HREF="page49.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1819" HREF="page53.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1829" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS>
<img src="../icons/bruno.gif" alt="Bruno" align=right>
<a href="../copyright.html">Copyright &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>