The following multithreaded algorithm computes transpose of a matrix in parallel:

p Trans (X, Y, N)

if N = 1

then Y[1, 1] ← X [1, 1]

else partition X into four (N/2) × (N/2) submatrices X₁₁, X₁₂, X₂₁, X₂₂

partition Y into four (N/2) × (N/2) submatrices Y₁₁, Y₁₂, Y₂₁, Y₂₂

spawn p Trans (X₁₁, Y₁₁, N/2)

spawn p Trans (X₁₂, Y₁₂, N/2)

spawn p Trans (X₂₁, Y₂₁, N/2)

spawn p Trans (X₂₂, Y₂₂, N/2)

What is the asymptotic parallelism of the algorithm?

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) Dec 2019 Paper

Attempt Online

Answer 1

During transpose of the matrix, it is partitioned into 4 submatrices of size N/2.

If n = 1, then T(1) = 1

Else T₁(n) = 4T₁(N/2) + O(1) ----- (1)

Solving equation 1 by master’s theorem:

\({n^{log_b^a}} = \;{n^{log_2^4}} = {n^2}\), here a= 4 and b = 2

So, T₁(n) = O(N²)

But the algorithm is multithreaded, and transposing is going in parallel. And we solved one subproblem already.

So, T_n(N) = T_n(N/2) + O(1)

T_n(N) becomes O(log N)

asymptotic parallelism of the algorithm:

T₁/T_∞ or θ (N²/lg N)