Define Asymptotic Run Time of Parallel Algorithm

Question

I am newbie to understanding Parallel Algorithms. Can someone please explain in simple words [or examples] what Asymptotic Run Time of a Parallel Algorithm means?

Context: If the best known sequential algorithm for a problem π has an asymptotic run time of S(n) and if T(n,p) is the asymptotic run time of a parallel algorithm, then the asymptotic speedup of the parallel algorithm is defined as S(n)/T(n,p) If S(n)/T(n,p) = Ɵ(p), then the algorithm is said to have linear speed up.

Answer 1

The asymptotic run time of a parallel algorithm usually means the time required for an algorithm with p processors to give a correct solution. But, the analysis of an algorithm always depends on the model you are using. A satisfactory answer to your question would become too long. I strongly recommend you to read chapter 27 of Introduction to Algorithms. It is an excellent text to understand the analysis of parallel algorithms. In the first few pages you probably would find the answer to your question.