In computer science, analysis of parallel algorithms is the process of finding the computational complexity of algorithms executed in parallel – the amount of time, storage, or other resources needed to execute them.
A so-called work-time (WT) (sometimes called work-depth, or work-span) framework was originally introduced by Shiloach and Vishkin [1] for conceptualizing and describing parallel algorithms.
The inclusion of the suppressed information is guided by the proof of a scheduling theorem due to Brent,[2] which is explained later in this article.
For example, the WT framework was adopted as the basic presentation framework in the parallel algorithms books (for the parallel random-access machine PRAM model) [3] and, [4] as well as in the class notes .
Let Tp denote the time that expires between the start of the computation and its end.