        Next: Implementation Challenges Up: Introduction to Algorithms Previous: War Story: Psychic Modeling

# Exercises

1. Let P be a problem. The worst-case time complexity of P is . The worst-case time complexity of P is also . Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P?

• A has worst-case time complexity .
• A has worst-case time complexity .
• A has worst-case time complexity O(n).
• A has worst-case time complexity .
• A has worst-case time complexity .
2. Suppose that an algorithm A runs in worst-case time f(n) and that algorithm B runs in worst-case time g(n). For each of the following questions, answer either yes, no, or can't tell and explain why.

(a) Is A faster than B for all n greater than some if ?

(b) Is A faster than B for all n greater than some if ?

(c) Is A faster than B for all n greater than some if ?

(d) Is B faster than A for all n greater than some if ?

(e) Is B faster than A for all n greater than some if ?

(f) Is B faster than A for all n greater than some if ?

(a) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on some inputs?

(b) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on all inputs?

(c) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on some inputs?

(d) If I prove that an algorithm takes worst-case time, is it possible that it takes O(n) on all inputs?

(e) Is the function , where for even n and for odd n?

4. For each of the following, answer yes, no, or can't tell. Explain your reasoning!

(a) Is ?

(b) Is ?

(c) Is ?

(d) Is ?

5. (*) Give a proof or counterexample to the following claim: if f(n) = O(F(n)) and g(n) = O(G(n)), then f(n)/g(n) = O(F(n)/G(n)).
6. (*) Does f(n) = O(g(n)) imply that ? Explain your reasoning!
7. (*) Give a proof or counterexample to the following claim: for all functions f(n) and g(n), either f(n) = O(g(n)) or g(n) = O(f(n)).
8. (*) When you first learned to multiply numbers, you were told that means add x a total of y times, so . What is the time complexity of multiplying two n-digit numbers in base b (people work in base 10, of course, while computers work in base 2) using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. (hint: how big can y be as a function of n and b?)
9. (*) In grade school, you learned to multiply long numbers on a digit by digit basis, so that . Analyze the time complexity of multiplying two n-digit numbers with this method as a function of n (assume constant base size). Assume that single-digit by single-digit addition or multiplication takes O(1) time.        Next: Implementation Challenges Up: Introduction to Algorithms Previous: War Story: Psychic Modeling

Algorithms
Mon Jun 2 23:33:50 EDT 1997