UGC NET Computer Science December 2019 | Question 125

Question 125

---

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)x (N/2) submatrices X11,X12,X21,X22
partition Y into four (N/2)x(N/2) submatrices Y11,Y12,Y21,Y22.
spawn p Trans (X11,Y11,N/2)
spawn p Trans (X12,Y12,N/2)
spawn p Trans (X21,Y21,N/2)
spawn p Trans (X22,Y22,N/2)
What is the asymptotic parallelism of the algorithm?

1. 1. T₁/T_∞ or θ(N² / lg N)
2. 2. T₁/T_∞ or θ(N / lg N)
3. 3. T₁/T_∞ or θ(lg N / N²)
4. 4. T₁/T_∞ orθ(lg N/ N)

Answer : 1. T₁/T_∞ or θ(N² / lg N)

Explanation Question 125

Option 1 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 124	UGC NET CS December 2019 - Question 126