page62.html

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

We will confirm this result in Section&nbsp;<A HREF="page63.html#secasymptoticpolyi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> below.
<P>
The next theorem addresses the asymptotic behavior
of the product of two functions whose asymptotic behaviors are known:
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremiii">&#160;</A>
If  <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58677" SRC="img262.gif"  > and  <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58679" SRC="img263.gif"  >, then
<P> <IMG WIDTH=367 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath58668" SRC="img309.gif"  ><P></BLOCKQUOTE>
<P>
	extbfProof
By Definition&nbsp;<A HREF="page59.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, there exist two integers,  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58699" SRC="img269.gif"  > and  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58701" SRC="img270.gif"  >
and two constants  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58703" SRC="img271.gif"  > and  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58705" SRC="img272.gif"  > such that
 <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58707" SRC="img273.gif"  > for  <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58709" SRC="img274.gif"  > and
 <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58711" SRC="img275.gif"  > for  <IMG WIDTH=46 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58713" SRC="img276.gif"  >.
Furthermore, by Definition&nbsp;<A HREF="page59.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,
 <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif"  > and  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58683" SRC="img265.gif"  > are both non-negative for all integers  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >.
<P>
Let  <IMG WIDTH=120 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58715" SRC="img277.gif"  > and  <IMG WIDTH=62 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58857" SRC="img310.gif"  >.
Consider the product  <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58859" SRC="img311.gif"  > for  <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif"  >:
<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray1521" SRC="img312.gif"  ><P>
Thus,  <IMG WIDTH=230 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58863" SRC="img313.gif"  >.
<P>
Theorem&nbsp;<A HREF="page62.html#theoremiii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> describes a simple,
but extremely useful property of big oh.
Consider the functions  <IMG WIDTH=228 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58865" SRC="img314.gif"  > and 
 <IMG WIDTH=192 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58867" SRC="img315.gif"  >.
By Theorem&nbsp;<A HREF="page62.html#theoremiii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,
the asymptotic behavior of the product  <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58859" SRC="img311.gif"  >
is  <IMG WIDTH=139 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58871" SRC="img316.gif"  >.
That is, we are able to determine the asymptotic behavior of
the product without having to go through the gory details of
calculating that  <IMG WIDTH=326 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58873" SRC="img317.gif"  >.
<P>
The next theorem is closely related to the preceding one
in that it also shows how big oh behaves with respect to multiplication.
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremiv">&#160;</A>
If  <IMG WIDTH=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58677" SRC="img262.gif"  > and  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif"  > is a function whose value is non-negative
for integers  <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif"  >,
then
<P> <IMG WIDTH=367 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath58669" SRC="img318.gif"  ><P></BLOCKQUOTE>
<P>
	extbfProof
By Definition&nbsp;<A HREF="page59.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, there exist integers  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58491" SRC="img235.gif"  >
and constant  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58883" SRC="img319.gif"  > such that
 <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58885" SRC="img320.gif"  > for  <IMG WIDTH=47 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58525" SRC="img239.gif"  >.
Since  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif"  > is never negative,
<P> <IMG WIDTH=393 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath58670" SRC="img321.gif"  ><P>
Thus,  <IMG WIDTH=230 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58891" SRC="img322.gif"  >.
<P>
Theorem&nbsp;<A HREF="page62.html#theoremiv"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> applies when we multiply a function,  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif"  >,
whose asymptotic behavior is known to be  <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58729" SRC="img282.gif"  >,
by another function  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif"  >.
The asymptotic behavior of the result is simply  <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58899" SRC="img323.gif"  >.
<P>
One way to interpret Theorem&nbsp;<A HREF="page62.html#theoremiv"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>
is that it allows us to do the following mathematical manipulation:
<P> <IMG WIDTH=500 HEIGHT=40 ALIGN=BOTTOM ALT="eqnarray1533" SRC="img324.gif"  ><P>
That is, Fallacy&nbsp;<A HREF="page61.html#fallacyi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> notwithstanding,
we can multiply both sides of the ``equation'' by  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif"  >
and the ``equality'' still holds.
Furthermore, when we multiply  <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58729" SRC="img282.gif"  > by  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif"  >,
we simply bring the  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58691" SRC="img266.gif"  > inside the  <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif"  >.
<P>
The last theorem in this section
introduces the <em>transitive property</em> of big oh:
<P>
<BLOCKQUOTE> <b>Theorem (Transitive Property)</b><A NAME=1539>&#160;</A>
<A NAME="theoremv">&#160;</A>
If <I>f</I>(<I>n</I>)=<I>O</I>(<I>g</I>(<I>n</I>)) and <I>g</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>))
then <I>f</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>)).
</BLOCKQUOTE>
<P>
	extbfProof
By Definition&nbsp;<A HREF="page59.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, there exist two integers,  <IMG WIDTH=15 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58699" SRC="img269.gif"  > and  <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58701" SRC="img270.gif"  >
and two constants  <IMG WIDTH=12 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58703" SRC="img271.gif"  > and  <IMG WIDTH=13 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58705" SRC="img272.gif"  > such that
 <IMG WIDTH=95 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58925" SRC="img325.gif"  > for  <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58709" SRC="img274.gif"  > and
 <IMG WIDTH=95 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58929" SRC="img326.gif"  > for  <IMG WIDTH=46 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline58713" SRC="img276.gif"  >.
<P>
Let  <IMG WIDTH=120 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58715" SRC="img277.gif"  > and  <IMG WIDTH=62 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline58857" SRC="img310.gif"  >. Then
<P> <IMG WIDTH=500 HEIGHT=64 ALIGN=BOTTOM ALT="eqnarray1544" SRC="img327.gif"  ><P>
Thus, <I>f</I>(<I>n</I>)=<I>O</I>(<I>h</I>(<I>n</I>)).
<P>
The transitive property of big oh
is useful in conjunction with Theorem&nbsp;<A HREF="page62.html#theoremii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.
Consider  <IMG WIDTH=81 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58939" SRC="img328.gif"  > which is clearly  <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif"  >.
If we add to  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58681" SRC="img264.gif"  > the function  <IMG WIDTH=81 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58945" SRC="img330.gif"  >,
then by Theorem&nbsp;<A HREF="page62.html#theoremii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,
the sum  <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58719" SRC="img279.gif"  > is  <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58801" SRC="img303.gif"  >
because  <IMG WIDTH=170 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58951" SRC="img331.gif"  >.
That is,  <IMG WIDTH=174 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58953" SRC="img332.gif"  >.
The combination of the fact that  <IMG WIDTH=98 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58955" SRC="img333.gif"  >
<em>and</em> the transitive property of big oh,
allows us to conclude that the sum is  <IMG WIDTH=40 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58941" SRC="img329.gif"  >.
<P>
<HR><A NAME="tex2html1925" HREF="page63.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1923" HREF="page59.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1917" HREF="page61.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html1927" 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>