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

A Simple Example


Consider the function f(n)=8n+128 shown in Figure gif. Clearly, f(n) is non-negative for all integers tex2html_wrap_inline58277. We wish to show that tex2html_wrap_inline58309. 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_inline58317.

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


Since (n+8)>0 for all values of tex2html_wrap_inline58277, we conclude that tex2html_wrap_inline58325. That is, tex2html_wrap_inline58327.

So, we have that for c=1 and tex2html_wrap_inline58327, tex2html_wrap_inline58317 for all integers tex2html_wrap_inline58299. Hence, tex2html_wrap_inline58309. Figure gif clearly shows that the function tex2html_wrap_inline58339 is greater than the function f(n)=8n+128 to the right of n=16.

Of course, there are many other values of c and tex2html_wrap_inline58265 that will do. For example, c=2 and tex2html_wrap_inline58351 will do, as will c=4 and tex2html_wrap_inline58355. (See Figure gif).

Figure: Showing that tex2html_wrap_inline58387.

next up previous contents index

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