Due Date: January 16, 2k+1
Problems: 1.2; 2.7

1.2:

Number of computations: n * n * (n + n - 1)
Number of values obtained from memory: n * n + n * n

ratio = (2*n^3 - n^2) / 2 / n^2 = n - 1/2


2.7:

T(1) = N (proportionality factor = 1)
T(P) = c * (N / P + (s + 1) * P) where c is the proportionality factor

S(P) = T(1) / T(P) = 1 / c / (N / P + (s + 1) * P) 

E(P) = S(P) / P = 1 / c / (N + (s + 1) * P^2)   (1)
E(P) >= 1 - g                                   (2)


(1) and (2) =>

 P^2 <= N / (s + 1) * (1 - c * (1 - g)) / c / (1 - g)
 Because P^2 >= 0, in order to have a solution right term must be also >=0

 So, 1 - g > 0 and 1 - c * (1 - g) > 0 => c < 1 / (1-g)      (3)
 or  1 - g < 0 and 1 - c * (1 - g) < 0 => not an interesting case


Best P is max integer less than (N / (s + 1) * (1 - c * (1 - g)) / c / (1 - g))^(1/2) 
with conditions (3)