Last update: June 26, 11:00AM.

Note: No late homework will be accepted.

Note: You are responsible for reading and understanding the course policy on academic integrity. Re-read it before continuing.

1. Let s(n)=0+1+2+3+...+n, that is, the function which takes n and returns the sum of the first n positive integers.
   
   1. Give a simple, informal argument that s(n) is O(n²). Note: We mean the mathematical function s(n). We do not mean the running time of an algorithm to compute s(n).
   2. Prove by induction that s(n) = n(n+1)/2 (for all n greater than or equal to 0).
   3. Use the result of the previous part to conclude formally that s(n) is Theta(n²) by providing values for n₀ and c in the formal definition of asymptotic notation.
   4. Assume you are given an array of n integers and you are told that each of the numbers 0, 1, 2, ..., n appears once in the array, except for the absence of one number. Develop an algorithm to determine the missing number that: does not modfiy the input array, runs in time O(n), and uses only O(1) additional space. (Hint: Use the second part of this problem.)
   
   
   
2. Let b and d be constants.
   1. Prove that log_bn is O(log_dn). Use the formal definition of O, take n₀ to be 1, and develop a value for c. (Hint: see page 34 of the text.)
   2. Conclude that in fact log_bn is Theta(log_dn). (This is trivial; explain why).
   3. What is the numerical value for c when b=10 and d=2?
      What is the numerical value for c when b=5000 and d=2?
      (Use a calculator.)
   
   
   
3. Prove that mn is O((max(m,n))²).
   
   
4. Text exercise 4.2-4 on page 61.
   
   
5. Text exercise 4.3-1 on page 64.
   
   
6. Assume a₁+a₂ < 1. Prove T(n) = T(a₁n) + T(a₂n) + bn is O(n).
   (Hint: Use induction and express c in terms of a₁, a₂, and b. Assume T(1) = 1. Where do you use the fact that a₁ + a₂ < 1?)
   
   
7. Give a tight asymptotic bound for the following recurrence: T(n) = 2T(n-1) + O(1).
   
   For fun: Use a humorous non-technical sentence to describe the size of T(500) for the recurrence defined above.