Discrete Mathematics for Computer Science

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). Deter-

mine 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)