Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

A Simple Example

Consider the function tex2html_wrap_inline59163 which is shown in Figure gif. Clearly, f(n) is non-negative for all integers tex2html_wrap_inline58277. We wish to show that tex2html_wrap_inline59169. According to Definition gif, in order to show this we need to find an integer tex2html_wrap_inline58265 and a constant c>0 such that for all integers tex2html_wrap_inline58299, tex2html_wrap_inline59177.

As with big oh, it does not matter what the particular constants are--as long as they exist! For example, suppose we choose c=1. Then

eqnarray1751

Since tex2html_wrap_inline59181 for all values of tex2html_wrap_inline58277, we conclude that tex2html_wrap_inline59185.

So, we have that for c=1 and tex2html_wrap_inline59185, tex2html_wrap_inline59177 for all integers tex2html_wrap_inline58299. Hence, tex2html_wrap_inline59169. Figure gif clearly shows that the function tex2html_wrap_inline58339 is less than the function f(n)=5n-64n+256 for all values of tex2html_wrap_inline58277. Of course, there are many other values of c and tex2html_wrap_inline58265 that will do. For example, c=2 and tex2html_wrap_inline58327.

   figure1754
Figure: Showing that tex2html_wrap_inline59241.

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.