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 undecidability 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 programming structures, such as sequence, selection, and repetition, can have functions defined
directly from the code that describes the complexity of these programming structures. Finally, 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
IG- HI E O(F)
5.3 Summary
TERMS
approximating curve
Complexity of Sequence
looping
average time complexity
Control Structures
nondeterministic polynocertificate
decision problem
mial time (ArP)
Complexity of Repetition
iteration
parallel and distributed
Complexity of Selection
key operations
algorithms
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 undecidability 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 programming structures, such as sequence, selection, and repetition, can have functions defined
directly from the code that describes the complexity of these programming structures. Finally, 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
IG- HI E O(F)
5.3 Summary
TERMS
approximating curve
Complexity of Sequence
looping
average time complexity
Control Structures
nondeterministic polynocertificate
decision problem
mial time (ArP)
Complexity of Repetition
iteration
parallel and distributed
Complexity of Selection
key operations
algorithms