322
CHAPTER 5 Analysis of Algorithms
polynomial time (7P)
selection
time complexity
propositional satisfiability
sequence
verifier algorithm V
repetition
space complexity
worst-case behavior
satisfiable
structured programming
worst-case complexity
ALGORITHMS
BubbleSort I
Ordering Three Values II
BubbleSort II
Ordering Three Values III
Detecting Order for Three Values
Selection Sort
Ordering Three Values I
5.5 Summary
TERMS
algorithm
function call
total algorithm
decidable
halting problem
undecidable
decision algorithm
reduction
universal Turing mechine
decision problem
return value
ALGORITHMS
Existence of Universal Algorithm, Turing
Unsolvability of the Halting Problem,
NegSelfRef
Turing
5.6.2 Starting to Review
1. Express in words what G e O(F) means. Express in words what G 0 O(F) means.
2. Let F(n) = n and G(n) = 2n - 3 be functions defined on [0, oo). Find a real number
c and an No E N such that F E O(G).
3. Let F(n) = n and G(n) = 2n + 3 be functions defined on [0, cc). Find a real number
c and an No E N such that F e O(G).
4. Let F(n) = n and G(n) = n
2 + 3 be functions defined on [0, cc). Show that F E 0(G)
but G 0• O(F).
5. Show that 0(1) g 0(log (n)).
6. Let F(x) = 7x be a function defined on [0, oo). Find a real number c and an No e N
such that F e 0(a
2 ).
7. Let F(n) = n
2 - n + 550 and G(n) = 59n + 50 be function defined on [0, oo). Determine n such that F takes less time at n than G.
8. Show that E-n 0 i2 E 0(n
3 ). Conjecture about the complexity of
0 im for m e N.
9. Explain in words how the complexity of a sequence of statements is computed.
10. Explain in words how the complexity of a selection statement of the form if-then-else
is computed.
11. Explain in words how the complexity of a loop of the form for i = 0 to n is computed.
5.6.3 Review Questions
Prove the following set of inclusions:
O(1) C O(log(n)) C 0(JHn) C 0(n) C 0(n log(n))
C O(n
2 ) C 0(2n) C 0(n . 2n) C 0(3n) C 0(n!) C 0(nn)