Questão 1510865

Observe o seguinte algoritmo direto baseado na paralelização dos laços no procedimento SQUARE - MATRIX - MULTIPLY:

P-SQUARE-MATRIX-MULTIPLY (A,B)

1 __ n = A.rows

2 __ seja C uma nova matriz n x n

3__ parallel for i = 1 to n

4 __ __ __ parallel for j = 1 to n

5 __ __ __ __ c_ij = 0

6 __ __ __ __ for k =1 to n

7 __ __ __ __ __ __ c_ij = c_ij + a_ik . b_kj

8 __ return C

Pode-se afirmar que a duração é T∞(n) = (n), devido às descidas dos laços parallel for e for comum, resultando em uma duração total de (lg n) + (lg n) + (n) = (n). Desse modo, qual é o paralelismo?