$4+3$ points$)$ On an EREW PRAM, consider an algorithm that add the numbers in array A using p $<=$ n processors as follows: The array is split into n$/$p size subarrays. Each processor finds a local sum of its subarray $($P i working on ith subarray$).$ Then a reduction tree is used on p local sums to find the global sum. For this algorithm,

i$.$ Calculate parallel time T p and work done. Give expressions for speedup S p and the cost of this

algorithm. Only order notation is needed.

ii$.$ Show that this algorithm achieves cost optimality for processors in the range $1$ through O$($ long n $).$