CS410, Summer 1998
Homework 1 Sample Solution
Prepared by Dan Grossman

1. Let s(n) = 0+1+2+3+...+n.

  1. Claim: s(n) is O(n^2).
     Informal argument: s(n) = 0+1+2+3+...+n <= n+n+n+...+n because
     every term is less than or equal to n.  Since there are n+1 terms in the 
     sum, this sum of n's equals n*(n+1) = n^2 + n which is O(n^2).
 
  2. Claim: s(n) = n(n+1)/2 (for all n>=0).
     Proof: By induction on n.  
     
     Our inductive hypothesis P(n) is that s(n)=n(n+1)/2.
     
     For the base case let n=0.  Then s(n) = 0 because the summation
     has exactly one term.  Also n(n+1)/2 = 0(0+1)/2 = 0.  So s(n) =
     n(n+1)/2.

     For the inductive case we assume P(n-1) and prove P(n):
	s(n) = 0+1+2+3+...+n		by definition of s(n)
	     = s(n-1) + n		by definition of s(n-1)
	     = (n-1)(n-1+1)/2 + n	by P(n-1)
	     = (n-1)n/2 + n		by math
	     = n^2/2 - n/2 + n		
	     = n^2/2 + n/2
	     = n(n+1)/2
     and we are done.

    3. We just proved s(n) = n(n+1)/2.  So we just show that n(n+1)/2
       is O(n^2).  This is obvious by looking at the leading term, but
       we are asked to provide values for N and c.  By inspection, for
       n > 0, n(n+1)/2 < 1n^2.  That is, it suffices to let N = 1 and c = 1.
       Notice how this is not quite true if N = 0.

       We can prove our "inspection" by again using induction:
       Claim: For all n > 1, n(n+1)/2 < n^2
       Proof: By induction on n with inductive hypothesis 
		P(n) being n(n+1)/2 < n^2
       For the base case, let n = 2.  Immediately, 2(2+1)/2 = 3 < 4 = 2^2.
       For the inductive case, assume P(n-1) and prove P(n):
	n(n+1)/2 =  (n-1)(n-1+1)/2 + n	by math -- reverse of last proof
		 <  (n-1)^2 + n		by P(n-1) and adding n to both sides
		 =  n^2 - 2n + 1 + n	by math
		 =  n^2 - n + 1
		 <  n^2			because n > 1 (in fact n > 2)
       and we are done.

	For the lower bound, just let c = 1/4 and everything is straightforward.

    4. Here's a Java implementation:
	int findMissing (int [] arr) {
	     int n	   = arr.length;
	     int sumLeft   = n*(n+1)/2;
	     for (int i = 0; i < n; i++) {
		sumLeft -= arr[i];
	     }
	     return sumLeft;
	}

2. Let b and d be constants.
     1. Claim: log_b n is O(log_d n).
        Proof: We know from math that log_b n = log_d n / log_d b for
	       all n.  But log_d b is a constant.  So we are done immediately 
	       with N=0 and c = log_d b.
 
     2. Claim: log_b n is Theta(log_d n).
	Proof: We showed log_b n is O(log_d n).  But b and d are both
	just constants so we know by symmetry that log_d n is O(log_b n).
	Then log_b n is Theta(log_d n).  (To be completely technical,
        we can break the last step into parts and use theorems from
	the text.  By transpose symmetry (page 31), log_b n is Omega(log_d n).
	Then by Theorem 2.1, log_b n is Theta(log_d n).)

3. Claim: mn is O((max(m,n))^2).
   Proof: Either m < n or n <= m.  
	  If m < n, max(m,n) = n, so (max(m,n))^2 = n^2.  
		So we have to show mn is O(n^2).  Since m < n, mn < n^2 which
		is O(n^2) so we are done.
	  If n <= m, max(m,n) = m, so (max(m,n))^2 = m^2.  
		So we have to show mn is O(m^2).  Since n < m, mn < m^2 which
		is O(m^2) so we are done.

4. Use iteration to solve T(n) = T(n-a) + T(a) + n where a >= 1 is a constant:
   T(n) = T(n-a) + T(a) + n
	= T(n-2a) + T(a) + n-a + T(a) + n 
	= T(n-3a) + T(a) + n-2a + T(a) + n-a + T(a) + n
	= ...
	= sum from i=0 to n/a of T(a) + n-ai
	= n/a(T(a)) + n/a(n) - a(sum from i = 0 to n/a of i)
	= n/a(T(a)) + n/a(n) - a*(n/a)(n/a + 1)/2
	= n/a(T(a)) + n^2/a - n^2/2a + n/2a^2
	= n^2/2a + O(n)
	= O(n^2)
    Notice that by closing the summation with math, we don't need to do a proof
    by induction.  Not that there's anything wrong with proof by induction. :-)

5. Use the master method to give tight bounds for the following:

   a. T(n) = 4 T(n/2) + n
	a = 4, b = 2, so log_b a = 2, and n < n^2, so case 1 applies and
	T(n) is Theta(n^2).

   b. T(n) = 4T(n/2) + n^2
	Calculations as above but now case 2 applies, so
	T(n) is Theta(n^2log n).

   c. T(n) = 4T(n/2) + n^3
	You guessed it, case 3 applies, so
	T(n) is Theta(n^3)

6. Let T(n) = T(a_1 n) + T(a_2 n) + bn where a_1 + a_2 < 1.
   Claim: T(n) is O(n).
   Proof: By induction on n.
   Our inductive hypothesis P(n) is that T(n) < cn for some 
   constant c.  We will define c as we complete the proof.
   For the base case, we know T(1) = 1.  So P(1) is satisfied as long as c > 1.
   For the inductive case, we assume P(m) for all m < n and prove P(n).  
   Notice this is a strong induction.
	T(n) = T(a_1 n) + T(a_2 n) + bn
	     < ca_1 n + ca_2 n + bn	by P(a_1 n) and P(a_2 n)
	     = c(a_1 + a_2) n + bn	by math
   So we are done if c(a_1 + a_2)n + bn	< cn
		     c(a_1 + a_2) + b   < c
				    b   < c (1 - a_1 - a_2)
		     b/ (1 - a_1 - a_2) < c
   Notice this last step works only because a_1 + a_2 < 1.  Otherwise,
   we would be dividing by a negative and the inequality would flip!
  
   Since b, a_1, and a_2 are constants, we can use this value of c.
   In conclusion, the proof works so long as c > max(1, b/(1-a_1-a_2)).

7. T(n) = 2T(n-1) + O(1) is Theta(2^n).  This is most easily seen by
drawing a recursion tree.  

2^500 is so big that that it makes my brain feel fuzzy when I think about it.