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 ?

3. For each of these questions, briefly explain your answer.

   (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.