page60.html

wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq

means that, given any arbitrary positive value  <IMG WIDTH=6 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap_inline59319" SRC="img299.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img299.gif"  >,
it is possible to find a value  <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"  >
such that for all  <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"  >
<P> <IMG WIDTH=305 HEIGHT=40 ALIGN=BOTTOM ALT="displaymath59217" SRC="img300.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img300.gif"  ><P>
<P>
Thus, if we chose a particular value, say  <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline59325" SRC="img301.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img301.gif"  >,
then there exists a corresponding  <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"  > such that
<P> <IMG WIDTH=500 HEIGHT=105 ALIGN=BOTTOM ALT="eqnarray1426" SRC="img302.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img302.gif"  ><P>
<P>
Consider the sum  <IMG WIDTH=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59305" SRC="img294.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img294.gif"  >:
<P> <IMG WIDTH=500 HEIGHT=87 ALIGN=BOTTOM ALT="eqnarray1430" SRC="img303.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img303.gif"  ><P>
where  <IMG WIDTH=138 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59331" SRC="img304.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img304.gif"  >.
Thus,  <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59317" SRC="img297.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img297.gif"  >.
<P>
Consider a pair of functions  <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"  > and  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif"  >,
which are 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"  > and  <IMG WIDTH=59 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59281" SRC="img286.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img286.gif"  >, respectively.
According to Theorem&nbsp;<A HREF="page60.html#theoremi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremi"><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=144 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59305" SRC="img294.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img294.gif"  > is  <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59285" SRC="img287.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img287.gif"  >.
However, 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> says that,
if  <IMG WIDTH=140 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img305.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img305.gif"  > exists,
then the sum <I>f</I>(<I>n</I>) is simply  <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"  > which,
by the transitive property (see Theorem&nbsp;<A HREF="page60.html#theoremv" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremv"><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> below), is  <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"  >.
<P>
In other words, if the ratio  <IMG WIDTH=80 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59355" SRC="img307.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img307.gif"  >
asymptotically approaches a constant as <I>n</I> gets large,
we can say that  <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_inline59279" SRC="img285.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img285.gif"  >,
which is often a lot simpler than  <IMG WIDTH=146 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59285" SRC="img287.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img287.gif"  >.
<P>
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> is particularly useful result.
Consider  <IMG WIDTH=72 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59365" SRC="img308.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img308.gif"  > and  <IMG WIDTH=72 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59177" SRC="img260.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img260.gif"  >.
<P> <IMG WIDTH=500 HEIGHT=95 ALIGN=BOTTOM ALT="eqnarray1437" SRC="img309.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img309.gif"  ><P>
From this we can conclude that  <IMG WIDTH=228 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59369" SRC="img310.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img310.gif"  >.
Thus, 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> suggests that
the sum of a series of powers of <I>n</I> is  <IMG WIDTH=45 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59373" SRC="img311.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img311.gif"  >,
where <I>m</I> is the largest power of <I>n</I> in the summation.
We will confirm this result in Section&nbsp;<A HREF="page61.html#secasymptoticpolyi" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page61.html#secasymptoticpolyi"><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> 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=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=117 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59229" SRC="img266.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img266.gif"  >, then
<P> <IMG WIDTH=367 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath59218" SRC="img312.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img312.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 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=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59257" SRC="img276.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img276.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=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59261" SRC="img278.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img278.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"  >.
Furthermore, 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>,
 <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"  > and  <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59233" SRC="img268.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img268.gif"  > are both non-negative for all 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"  >.
<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"  >.
Consider the product  <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59409" SRC="img314.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img314.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"  >:
<P> <IMG WIDTH=500 HEIGHT=39 ALIGN=BOTTOM ALT="eqnarray1455" SRC="img315.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img315.gif"  ><P>
Thus,  <IMG WIDTH=230 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59413" SRC="img316.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img316.gif"  >.
<P>
Theorem&nbsp;<A HREF="page60.html#theoremiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremiii"><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> describes a simple,
but extremely useful property of big oh.
Consider the functions  <IMG WIDTH=228 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59415" SRC="img317.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img317.gif"  > and 
 <IMG WIDTH=192 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59417" SRC="img318.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img318.gif"  >.
By Theorem&nbsp;<A HREF="page60.html#theoremiii" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page60.html#theoremiii"><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 asymptotic behavior of the product  <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59409" SRC="img314.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img314.gif"  >
is  <IMG WIDTH=139 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59421" SRC="img319.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img319.gif"  >.
I.e., 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=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59423" SRC="img320.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img320.gif"  >.
<P>
The next theorem is closely related to the preceding one