page60.html

wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq

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=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59227" SRC="img265.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img265.gif"  > and  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif"  > is a function whose value is non-negative
for integers  <IMG WIDTH=38 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59063" SRC="img241.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img241.gif"  >,
then
<P> <IMG WIDTH=366 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath59219" SRC="img321.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img321.gif"  ><P></BLOCKQUOTE>
<P>
	extbfProof
By Definition&nbsp;<A HREF="page57.html#defnbigoh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>, there exist integers  <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59043" SRC="img238.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img238.gif"  >
and constant  <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59433" SRC="img322.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img322.gif"  > such that
 <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59435" SRC="img323.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img323.gif"  > for  <IMG WIDTH=46 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59075" SRC="img242.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img242.gif"  >.
Since  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif"  > is never negative,
<P> <IMG WIDTH=393 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath59220" SRC="img324.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img324.gif"  ><P>
Thus,  <IMG WIDTH=230 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59441" SRC="img325.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img325.gif"  >.
<P>
Theorem&nbsp;<A HREF="page60.html#theoremiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremiv"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> applies when we multiply a function,  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif"  >,
whose asymptotic behavior is known to be  <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59279" SRC="img285.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img285.gif"  >,
by another function  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif"  >.
The asymptotic behavior of the result is simply  <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59449" SRC="img326.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img326.gif"  >.
<P>
One way to interpret Theorem&nbsp;<A HREF="page60.html#theoremiv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremiv"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is that it allows us to do the following mathematical manipulation:
<P> <IMG WIDTH=500 HEIGHT=39 ALIGN=BOTTOM ALT="eqnarray1467" SRC="img327.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img327.gif"  ><P>
I.e., Fallacy&nbsp;<A HREF="page59.html#fallacyi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page59.html#fallacyi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> notwithstanding,
we can multiply both sides of the ``equation'' by  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif"  >
and the ``equality'' still holds.
Furthermore, when we multiply  <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59279" SRC="img285.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img285.gif"  > by  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif"  >,
we simply bring the  <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59241" SRC="img269.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img269.gif"  > inside the  <IMG WIDTH=28 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58163" SRC="img1.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/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=1473>&#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="page57.html#defnbigoh" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html#defnbigoh"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>, there exist two integers,  <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59249" SRC="img272.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img272.gif"  > and  <IMG WIDTH=16 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59251" SRC="img273.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img273.gif"  >
and two constants  <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59253" SRC="img274.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img274.gif"  > and  <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59255" SRC="img275.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img275.gif"  > such that
 <IMG WIDTH=94 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59475" SRC="img328.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img328.gif"  > for  <IMG WIDTH=47 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59259" SRC="img277.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img277.gif"  > and
 <IMG WIDTH=96 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59479" SRC="img329.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img329.gif"  > for  <IMG WIDTH=47 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59263" SRC="img279.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img279.gif"  >.
<P>
Let  <IMG WIDTH=119 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59265" SRC="img280.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img280.gif"  > and  <IMG WIDTH=63 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59407" SRC="img313.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img313.gif"  >. Then
<P> <IMG WIDTH=500 HEIGHT=63 ALIGN=BOTTOM ALT="eqnarray1478" SRC="img330.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img330.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="page60.html#theoremii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Consider  <IMG WIDTH=81 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59489" SRC="img331.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img331.gif"  > which is clearly  <IMG WIDTH=39 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59491" SRC="img332.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img332.gif"  >.
If we add to  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59231" SRC="img267.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img267.gif"  > the function  <IMG WIDTH=81 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59495" SRC="img333.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img333.gif"  >,
then by Theorem&nbsp;<A HREF="page60.html#theoremii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremii"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
the sum  <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59269" SRC="img282.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img282.gif"  > is  <IMG WIDTH=60 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59351" SRC="img306.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img306.gif"  >
because  <IMG WIDTH=169 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59501" SRC="img334.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img334.gif"  >.
I.e.,  <IMG WIDTH=174 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59503" SRC="img335.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img335.gif"  >.
The combination of the fact that  <IMG WIDTH=98 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59505" SRC="img336.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img336.gif"  >
<em>and</em> the transitive property of big oh,
allows us to conclude that the sum is  <IMG WIDTH=39 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59491" SRC="img332.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img332.gif"  >.
<P>
<HR><A NAME="tex2html2641" HREF="page61.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page61.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2639" HREF="page57.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page57.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2633" HREF="page59.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page59.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2643" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2644" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

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