Discrete Mathematics for Computer Science

Chapter Review 321

other than In(In). Otherwise, A does not halt; it just keeps on interpreting the computation

of In(In) forever.

Now suppose an algorithm B computes a total algorithm extending A. Then, B(B) is

defined. So, A(B) is defined and does not equal B(B). Therefore, B does not extend A-a

contradiction. 0

The reader should note how this argument resembles both the proof of the undecid-

ability of the halting problem and Cantor's second diagonal argument (in his proof of the

uncountability of the reals).

rnChapter Review

This chapter presents a formal way of deciding the level of difficulty of a program and then

uses these ideas to compare programs. The definition of what it means for one function to

asymptotically dominate another function is the start of this analysis. First, we deal with

proving the basic properties of this relation and with showing that polynomials of different

degrees are actually functions of different complexity. Next, we show how basic program-

ming structures, such as sequence, selection, and repetition, can have functions defined

directly from the code that describes the complexity of these programming structures. Fi-

nally, we describe the halting problem of Turing that proves there are programs for which

it is impossible even to determine if they terminate.

5.6.1 Terms, Theorems, and Algorithms

5.1 Summary

TERMS

9 (F) exponential function order of F

algorithm halts polynomial function

asymptotic domination logarithmic function zero polynomial

degree O(F)

THEOREMS

F E 0(aF) andaF E O(F) F E O(G) if and only if O(F) g O(G)

HE O(G) and G E O(F), then O(F) = O(G) if and only if F E O(G)

H E O(F) and G E O(F)

G E O(F) and H E O(F), then a" E 0(bn) and bn g 0(a') where 1 <

G+HEO(F) a <b

G E O(F) and H E O(F), then

IG- HI E O(F)

5.3 Summary

TERMS

approximating curve Complexity of Sequence looping

average time complexity Control Structures nondeterministic polyno-

certificate decision problem mial time (ArP)

Complexity of Repetition iteration parallel and distributed

Complexity of Selection key operations algorithms