VLSI CAD - Spring 2008

Time Complexity Homework (50 points)

1. Prove the following:
   1.  
   2. If f(n)=Theta(g(n)) and g(n)=Theta(h(n)), then f(n)=Theta(h(n))
   3. If f(n)=O(g(n)) and g(n)=O(h(n)), then f(n)=O(h(n)).
2. As will be discussed in class, the binary search algorithm divides the list of numbers into two partitions, each 1/2 the size of the original list. We showed that the worst-case time complexity of the binary search is O(log n).
   1. Suppose that we modify the algorithm to divide the list into two partitions that are 1/3 and 2/3 the size of the original list. Prove that the worst-case time complexity is still O(log n). You have to present a formal proof.
   2. Would the time complexity change if the modified algorithm divides the list into partitions of sizes 1/k and (k-1)/k, assuming k<<n? Why?
   3. Now, suppose that the algorithm divides the list into two partitions of sizes C (e.g., C=3) and n-C (0<C<n). What is the worst-case time complexity? Prove your answer.
3. Prove that: n² + 100 n = Theta(n²).
4. If   f(n)=Omega(g(n)), does that mean g(n)=O(f(n))? Prove or disprove.
5. If f(n)= O(g(n)) and f(n)=Omega(h(n)), which one of the following could be true? (if true, give example functions of f, g and h, and also qualify when the case is true, e.g., "true for all instances of f, g, h", "not true for any instance of f, g, h", "true for some instances of f, g, h"):
   1. h(n)=O(g(n))
   2. g(n)=O(h(n))