Homework #1 Solution

(5 points)
```
Line_num
0	PolyEval(A,x)			|   |   |     |
1	  value = a0			|   |   |  1  |
2	  for i=1 to n-1		|   |   } n-1 |
3	     term = A[i]		|   | 1 }     |
4	     for j=1 to i		|   } i }     |
5		term = term * x		| 1 }   }     |
6     	  value = value + term		|   |   |  1  |
7        return value			|   |   |     |
```
Starting at the innermost loop and working out, we see that the j loop has a cost of 1 and executes i times on each iteration of the i loop. At the same level as the j loop is line 3, and we take the max, which is i . We see that the i loop executes n-1 times. At the same level as the i loop, we see that lines 1 and 6 each have a cost of 1, but again we take the max, giving us :
```
		  n-1
	T(n) = 	Sum(i) =  n( n-1) /2 
		 i = 1
```
the number of iterations is unaffected by the selected values of coefficients or of x, so the worst-case and best-case running times are the same, and we can say that T(n) = Theta(n^2).

Chapter 1, #14a & b (3 points)


	 k                 k    k	
	Sum (i * 2^i) =  Sum( Sum(2^j) ) 
	i=0               i=1  j=i

	 		   k    	
		       =  Sum(2^(k+1) - 2^i)
			  i=1
	 		                k    	
		       =  k*2^(k+1) -  Sum(2^i)
			               i=1  

		       =  k*2^(k+1) -  (2^(k+1) - 2)

		       =  (k-1)k*2^(k+1) + 2

14b.


	 k                 k    k	
	Sum (i * 2^-i) =  Sum( Sum(2^-j) ) 
	i=0               i=1  j=i

	 		   k    	
		       =  Sum(2^-i - 2-(k+1)) / (1 - 2^-1)
			  i=1  

		                      k 
		       = -k*2^(-k) + Sum(2^(-i+1))
	 		             i=1  


		       = -k*2^-k + 2 - 2^(-k+1)

		       = 2 - (k+2)*2^-k

Chapter 1, #16 (3 points)

	log_e n = log_2 n * log_e 2, so just multiply the binary log
by ln 2 = 0.693147

Chapter 1, #17 (3 points)

 17a.  Their product is 1 because ....

	b^(log_b a log_a b) =  (b^(log_b a))^log_a b 
		
			    =  a ^(log_a b)

			    = b

 17b.  log_a x = log_b x * log_a b < log_b x , since log_a b < 1 if a > b 

 17c.   Since n &ge 1 and the logarithmic functions are monotone increasing,

	log_b(n+c) &le log_b(nc) = log_b n + log_b c

     so the stated inequality holds with d = log_b c.

Chapter 1, #22 (3 points)

 22a.  False, by part(1) of the Growth Rates Theorem, with &alpha = 2.5 and &beta = 2.
 22b.  True, since lg(n^3) &isin &Omicron(log n) &sube &Omicron(n log n)
 22c.  True by the Growth Rates and Big-O Theorems, since &radic(n) &isin &Omicron(&radic(n)), 
lg &radic(n) = 1/2 lg n &isin &Omicron(n ^ (1/2)) = &Omicron(&radic(n)), and hence by multiplying 
the left and right sides &radic(n) lg &radic(n) &isin &Omicron(&radic(n) &radic(n)) = &Omicron(n).

Chapter 1, #23 (3 points)

 23a.   True.  For any n &ge 1, 2/n + 4/n^2 &le 2/n + 4/n = 6/n &isin &Omicron(1/n).
 23b.   True, since logarithms to different bases differ only by a constant factor.
 23c.  True, since logarithms of different powers of n differ only by a constant factor.
 23d.  False, since log n ¬in &radic(log_2 n). (If it were true that log n &isin &radic(log_2 n), 
then log n / &radic(log_2 n) would be bounded by some constant  c , but taking the base 
of log n to be 2 this ratio is the monotone increasing function &radic(log_2 n). )
 23e.  True, since for n > 26 we have min(700, n^2) < 700 &isin &Omicron(1).

Chapter 1, #36 (6 points)

Using the Divide and Conquer Recurrence Theorem in the text ...

a.  a = 3, b = 2, and e=1, so T(n) &isin &Omicron(n^log_2 3).
b.  a = 3, b = 2, and e=2, so T(n) &isin &Omicron(n^2).
c.  a = 8, b = 2, and e=3, so T(n) &isin &Omicron(n^3 log n).
d.  a = 4, b = 3, and e=1, so T(n) &isin &Omicron(n^ log_3 4).
e.  a = 4, b = 3, and e=2, so T(n) &isin &Omicron(n^2).
f.  a = 9, b = 3, and e=2, so T(n) &isin &Omicron(n^2 log n).

Using our version of the "Master Method":

a.  a = 3, b = 2, and p=1, k=0, so Case I, and
	T(n) &isin &Omicron(n^log_2 3).
b.  a = 3, b = 2, and p=2, k=0, so Case III, and 
	T(n) &isin &Omicron(n^2).
c.  a = 8, b = 2, and p=3, k=0, so Case II, and
	T(n) &isin &Omicron(n^3 log n).
d.  a = 4, b = 3, and p=1, k=0, so Case I, and
	T(n) &isin &Omicron(n^ log_3 4).
e.  a = 4, b = 3, and p=2, k=0, so Case III, and
	T(n) &isin &Omicron(n^2).
f.  a = 9, b = 3, and p=2, k=0, so Case II, and
	T(n) &isin &Omicron(n^2 log n).

Chapter 1, #47 (3 points)

	36 possibilities (6 x 6)

	1, 1	 1, 2	 1, 3	 1, 4	 1, 5	 1, 6
	2, 1	 2, 2	 2, 3	 2, 4	 2, 5	 2, 6
	3, 1	 3, 2	 3, 3	 3, 4	 3, 5	 3, 6
	4, 1	 4, 2	 4, 3	 4, 4	 4, 5	 4, 6
	5, 1	 5, 2	 5, 3	 5, 4	 5, 5	 5, 6
	6, 1	 6, 2	 6, 3	 6, 4	 6, 5	 6, 6

	Sums of those 36 possibilities:

	2	3 	4	5	6	7
	3 	4	5	6	7	8
	4	5	6	7	8	9
	5	6	7	8	9	10
	6	7	8	9	10	11
	7	8	9	10	11	12

	sum	count	prob
	 2	1	1/36
	 3	2	2/36
	 4	3	3/36
	 5	4	4/36
	 6	5	5/36
	 7	6	6/36
	 8	5	5/36
	 9	4	4/36
	10	3	3/36
	11	2	2/36
	12	1	1/36

Chapter 2, #15 (3 points)

The outer loop is executed n times; on the ith iteration, the 
inner loop iterates i^2 times (since x must be reduced from
i to 0 by steps of 1/i).  So the whole program takes 


           n 
	&Theta( n * i^2 ) &sube &Theta(n^3 )
          i=i

Chapter 2, #17 (3 points)


             n-1	n	     	j              n-1	n	
T(n) =      &Sigma		&Sigma		&Sigma  c  	= c    &Sigma	&Sigma	j
             i=1	j=i+1     	k=1            i=1    j=i+1


                n-1    (n+i+1) (n-1)
	=  c   &Sigma  -----------------
                i=1            2

           c    n-1 
	=  -   &Sigma  (n^2 + n = i^2 - i)
           2    i=1           

           c                      n(n-1)(2n-1)    n(n-1)
	=  -  (  (n^2 + n)(n-1) - -----------  - ------  ) 
           2                          6            2 

           c                      
	=  -   n(n-1)(n+1) &isin &Theta(n^3)
           3

Chapter 2, #19 (3 points))

	floor(sqrt(n))	floor(sqrt(n))	j		floor(sqrt(n))	floor(sqrt(n))   
T(n) = &Sigma		&Sigma		&Sigma  c  = c	&Sigma  		&Sigma		j
	i=1 		j=1            k=1		i=1		j=1

	      floor(sqrt(n))    floor(sqrt(n))*( floor(sqrt(n))+1)
	= c  &Sigma                   ---------------------------------
	      i=1 		              2

	  c   
	= -  floor(sqrt(n))^2 (floor(sqrt(n))+1) &isin &Theta(n^ 3/2)
	  2

a.  a = 8, b = 2, p = 3, k=1, so case II, and 
	T(n) = &Theta(n^3 log^2 n)

b.  a = 3, b = 2, p = 1, k=0, so case I, and
	T(n) = &Theta(n^log_2 3)

c.  a = 3, b = 2, p = 2, k=0, so case III, and 
	T(n) = &Theta(n^2)
 
d.  a = 16, b = 2, p = 3, k=1, so case I, and
	T(n) = &Theta(n^4)
	
e.  a = 1, b = 10/9, p = 1, k=0, so case III, and
	T(n) = &Theta(n)