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

A Simple Example

Consider the function tex2html_wrap_inline58882 which is shown in Figure gif. Clearly, f(n) is non-negative for all integers tex2html_wrap_inline57996. We wish to show that tex2html_wrap_inline58888. According to Definition gif, in order to show this we need to find an integer tex2html_wrap_inline57984 and a constant c>0 such that for all integers tex2html_wrap_inline58018, tex2html_wrap_inline58896.

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

eqnarray1745

Since tex2html_wrap_inline58900 for all values of tex2html_wrap_inline57996, we conclude that tex2html_wrap_inline58904.

So, we have that for c=1 and tex2html_wrap_inline58904, tex2html_wrap_inline58896 for all integers tex2html_wrap_inline58018. Hence, tex2html_wrap_inline58888. Figure gif clearly shows that the function tex2html_wrap_inline58058 is less than the function f(n)=5n-64n+256 for all values of tex2html_wrap_inline57996. Of course, there are many other values of c and tex2html_wrap_inline57984 that will do. For example, c=2 and tex2html_wrap_inline58046.

   figure1748
Figure: Showing that tex2html_wrap_inline58960.


next up previous contents index

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