# matrix vector multiplication complexity recurrence equation

Given is the following homework problem:

With the following definitions:

$$T_P$$: the minimum time (measured in computation steps to execute the program on P processors ($$1 \leq P \leq \infty$$ )

$$T_1$$: the total amount of work

$$T_\infty$$: critical path length

Multiplications are denoted by M and additions are denoted by A.

I tried the following:

Work $$T_1$$:

$$M_1(n) = 4*M_1(n/2)+2*A_1(n/2)$$ (Because of the 4 multiplication and 2 additions, not sure about the n/2)

$$= 4*M_2(n/2)+O(n)$$

Take n = 2^k: $$M_1(2^k) = 4*M_1(2^{k-1}) + O(2^k)$$

$$= 4*M_1(2^{k-1}) + O(2^k)$$

$$= 4^2*M_1(2^{k-2}) + 4*O(2^{k-1}) + O(2^k)$$

$$= 4^k*M_1(1) + O( 2^{2} + 2^{3} + … + 2^{k} )$$

$$= O(4^k) = O(2^{2k}) = O({(2^k)}^2)$$

$$M_1(n) = O(n^2)$$

Critical path length $$T_\infty$$:

$$M_∞(n) = M_∞(n/2)+M_∞(n/2) = M_2(n/2)+O(log n)$$

Take n = 2^k: $$M_∞(2^k)$$

$$= M_∞(2^{k-1}) + O(k)$$

$$= M_∞(1) + O ( 2 + 3 + … + k)$$

$$= O( (k*(k+1)/2 )$$

$$= O(k^2)$$

$$M_∞(n) = O( log^2(n) )$$

Could you tell me where the mistakes are and how to improve it?