Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Algorithms Asymptotic Worst Case Time and Time Complexity Introduction
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 X11, X12, X21, X22
partition Y into four (N/2) × (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
T1/T∞ or θ (N2/lg N)
2
T1/T∞ or θ (N/lg N)
3
T1/T∞ or θ (1g N/N2)
4
T1/T∞ θ (lg N/N)