Thus, for 
, the total complexities for the parallel
connected components algorithm are
Clearly, the computational complexity is the best possible
asymptotically. As for the communication complexity, it seems that
intuitively a latency factor 
has to be incurred during each
merge operation, and hence the factor 
.
