The Role of Theory in Computer Science - Models of Computation: Exploring the Power of Computing - page 14

and say that “ g ( x ) is big Omega of f ( x ) ” or that it grows at least as rapidly in x as f ( x ) .
If f ( x )= O ( g ( x )) and g ( x )= O ( f ( x )) ,wewrite

f ( x )=Θ( g ( x )) or g ( x )=Θ( f ( x ))

and say that “ f ( x ) is big Theta of g ( x ) ”and“ g ( x ) is big Theta of f ( x ) ” or that the two
functions have the same rate of growth in x .

The big Oh notation is illustrated by the expressions for f 1 ( n ) and f 2 ( n ) above.
EXAMPLE 1.2.1 We s how t ha t f 1 ( n )= 4 . 5 n 2 + 3 n is O ( n k ) for any k ≥ 2 ;thatis, f 1 ( n )
grows no more rapidly than n k 2 . We also show that n k for k ≥ = O ( f 1 ( n )) for k ≤ 2 ;that

is, that n k 2 . From the above definitions it follows

that f 1 ( n )=Θ( n 2 ) ;thatis, f 1 ( n ) and n 2 have the same rate of growth. We say that f 1 ( n ) is a
quadratic function in n .
To prove the first statement, we need to exhibit a natural number n 0 and a constant K 0 > 0
such that for all n

grows no more rapidly than f 1 ( n ) for k ≤

K 0 n k . If we can show that f 1 ( n ) K 0 n 2 ,thenwehave ≥ n 0 , f 1 ( n ) ≤ ≤

K 0 n k shown f 1 ( n ) ≤ for all k ≥ 2 . To show the former, we must show the following for some

K 0 > 0 and for all n ≥ n 0 :

K 0 n 2
We t r y K 0 = 5 . 5 and find that the above inequality is equivalent to 3 n

4 . 5 n 2 + 3 n ≤

≤ n 2 or 3 ≤ n .Thus,we

can choose n 0 = 3 and we are done.
To prove the second statement, namely, that n k

= O ( f 1 ( n )) for k ≤

2 , we must exhibit a

n 1 , n k

natural number n 1 and some K 1 > 0 such that for all n

≥ ≤ K 2 f 1 ( n ) .Ifwecanshow

K 1 f 1 ( n ) , then we have shown n k

that n 2

≤ ≤ K 2 f 1 ( n ) . To show the former, we must show the

following for some K 1 > 0 and for all n

≥ n 1 :

K 1 ( 4 . 5 n 2 + 3 n )
Clearly, if K 1 = 1 / 4 . 5 the inequality holds for n

n 2 ≤

≥ 0 ,since 3 K 1 n is positive. Thus, we choose

n 1 = 0 and we are done.
EXAMPLE 1.2.2 We now show that the slightly more complex function f 2 ( n )= 3 n + 4 . 5 n 2
grows as 3 n ;thatis, f 2 ( n )=Θ( 3 n ) , an exponential function in n .Because 3 n

≤ f 2 ( n ) for

0 , it follows that 3 n = O ( f 2 ( n )) . To show that f 2 ( n )= O ( 3 n ) , we demonstrate that

all n

≥

2 ( 3 n ) holds for n

f 2 ( n ) ≤ ≥

4 . This is equivalent to the following inequality:
4 . 5 n 2 3 n

To prove this holds, we show that h ( n )= 3 n /n 2

≤

is an increasing function of n for n ≥ 2

and that h ( 4 ) 4 . 5 . To show that h ( n ) is an increasing function of n , we compute the ratio

r ( n )= h ( n + 1 ) /h ( n ) and show that r ( n )

≥

2 .But r ( n )= 3 n 2 / ( n + 1 ) 2 and ≥ 1 for n ≥

1 when 3 n 2 ( n + 1 ) 2 or when n ( n r ( n ) ≥ ≥ − 1 ) ≥ 1 / 2 , which holds for n ≥ 2 .Since

h ( 3 )= 3 and h ( 4 )= 81 / 16 > 5 , the desired conclusion follows.

1.3 Methods of Proof
In this section we briefly introduce several methods of proof that are used in this topic, namely,
proof by induction, proof by contradiction, and the pigeonhole principle. In the previous