page75.html

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

solve the recurrence,
and put the  <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif"  > back!
In this case, we need to solve the recurrence
<P> <IMG WIDTH=397 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath59863" SRC="img479.gif"  ><P>
<P>
In the previous chapter, we used successfully repeated substitution
to solve recurrences.
However, in the previous chapter, all of the recurrences only had
one instance of  <IMG WIDTH=28 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57757" SRC="img51.gif"  > on the right-hand-side--in this case there are two.
As a result, repeated substitution won't work.
<P>
There is something interesting about this recurrence:
It looks very much like the definition of the Fibonacci numbers.
In fact, we can show by induction on <I>n</I>
that  <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59925" SRC="img480.gif"  > for all  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >.
<P>
	extbfProof (By induction).
<P>
<b>Base Case</b>
There are two base cases:
<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray2116" SRC="img481.gif"  ><P>
<P>
<b>Inductive Hypothesis</b>
Suppose that  <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59925" SRC="img480.gif"  > for  <IMG WIDTH=112 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59931" SRC="img482.gif"  > for some  <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif"  >.
Then
<P> <IMG WIDTH=500 HEIGHT=88 ALIGN=BOTTOM ALT="eqnarray2121" SRC="img483.gif"  ><P>
Hence, by induction on <I>k</I>,  <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59925" SRC="img480.gif"  > for all  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >.
<P>
So, we can now say with certainty that
the running time of the recursive Fibonacci algorithm,
Program&nbsp;<A HREF="page75.html#progexamplem"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,
is  <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59941" SRC="img484.gif"  >.
But is this good or bad?
The following theorem shows us how bad this really is!
<P>
<BLOCKQUOTE> <b>Theorem (Fibonacci numbers)</b><A NAME="theoremasymptoticfibonacci">&#160;</A>
<A NAME=2133>&#160;</A><A NAME="theoremix">&#160;</A>
The Fibonacci numbers are given by the closed form expression
<P><A NAME="eqnfibonacci">&#160;</A> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="equation2135" SRC="img485.gif"  ><P>
where  <IMG WIDTH=106 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59943" SRC="img486.gif"  >
and  <IMG WIDTH=106 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59945" SRC="img487.gif"  >.
</BLOCKQUOTE>
<P>
	extbfProof (By induction).
<P>
<b>Base Case</b>
There are two base cases:
<P> <IMG WIDTH=500 HEIGHT=154 ALIGN=BOTTOM ALT="eqnarray2147" SRC="img488.gif"  ><P>
<P>
<b>Inductive Hypothesis</b>
Suppose that Equation&nbsp;<A HREF="page75.html#eqnfibonacci"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> holds
for  <IMG WIDTH=112 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59931" SRC="img482.gif"  > for some  <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59027" SRC="img353.gif"  >.
First, we make the following observation:
<P> <IMG WIDTH=500 HEIGHT=68 ALIGN=BOTTOM ALT="eqnarray2161" SRC="img489.gif"  ><P>
Similarly,
<P> <IMG WIDTH=500 HEIGHT=71 ALIGN=BOTTOM ALT="eqnarray2165" SRC="img490.gif"  ><P>
<P>
Now, we can show the main result:
<P> <IMG WIDTH=500 HEIGHT=185 ALIGN=BOTTOM ALT="eqnarray2171" SRC="img491.gif"  ><P>
<P>
Hence, by induction, Equation&nbsp;<A HREF="page75.html#eqnfibonacci"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
correctly gives  <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59871" SRC="img470.gif"  > for all  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >.
<P>
Theorem&nbsp;<A HREF="page75.html#theoremix"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives us that
 <IMG WIDTH=128 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59955" SRC="img492.gif"  >
where  <IMG WIDTH=106 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59943" SRC="img486.gif"  >
and  <IMG WIDTH=106 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59945" SRC="img487.gif"  >.
Consider  <IMG WIDTH=8 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline59961" SRC="img493.gif"  >.
A couple of seconds with a calculator should suffice to convince you
that  <IMG WIDTH=45 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59963" SRC="img494.gif"  >.
Consequently, as <I>n</I> gets large,  <IMG WIDTH=25 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59967" SRC="img495.gif"  > is vanishingly small.
Therefore,  <IMG WIDTH=85 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59969" SRC="img496.gif"  >.
In asymptotic terms, we write  <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59971" SRC="img497.gif"  >.
Now, since  <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59973" SRC="img498.gif"  >,
we can write that  <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59975" SRC="img499.gif"  >.
<P>
Returning to Program&nbsp;<A HREF="page75.html#progexamplem"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,
recall that we have already shown that its running time is
 <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59941" SRC="img484.gif"  >.
And since  <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59975" SRC="img499.gif"  >,
we can write that  <IMG WIDTH=228 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline59981" SRC="img500.gif"  >.
That is, the running time of the recursive Fibonacci program
grows <em>exponentially</em> with increasing <I>n</I>.
And that is really bad in comparison with the linear
running time of Program&nbsp;<A HREF="page75.html#progexamplel"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>!
<P>
Figure&nbsp;<A HREF="page75.html#figfibonacci"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the actual running times
of both the non-recursive and recursive algorithms
for computing Fibonacci numbers.<A NAME="tex2html100" HREF="footnode.html#2218"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>
Because the largest Python plain integer is 2147483647,
it is only possible to compute Fibonacci numbers up
to  <IMG WIDTH=134 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59985" SRC="img501.gif"  > before
the Python virtual machine starts computing with long integers
(at which point our model of computation no longer applies).
<P>
The graph shows that up to about <I>n</I>=30,
the running times of the two algorithms are comparable.
However, as <I>n</I> increases past 30,
the exponential growth rate of Program&nbsp;<A HREF="page75.html#progexamplem"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
is clearly evident.
In fact, the actual time taken by Program&nbsp;<A HREF="page75.html#progexamplem"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
to compute  <IMG WIDTH=22 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline59991" SRC="img502.gif"  > was in excess of SOMETHING!
<P>
<P><A NAME="2512">&#160;</A><A NAME="figfibonacci">&#160;</A> <IMG WIDTH=575 HEIGHT=322 ALIGN=BOTTOM ALT="figure2223" SRC="img503.gif"  ><BR>
<STRONG>Figure:</STRONG> Actual running times of Programs&nbsp;<A HREF="page75.html#progexamplel"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> and&nbsp;<A HREF="page75.html#progexamplem"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<BR>
<P><HR><A NAME="tex2html2072" HREF="page76.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2070" HREF="page72.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2064" HREF="page74.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2074" 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>