0
$\begingroup$

Given is the following homework problem:

enter image description here

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.