## Speedup

In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm.

It is defined by the following formula:

where:

*p* is the number of __processors__

*T1* is the execution time of the sequential __algorithm__

*Tp* is the execution time of the __parallel algorithm__ with *p* __processors__

Linear speedup or ideal speedup is obtained when *Sp* = *p* . When running an algorithm with linear speedup, doubling the number of processors doubles the speed, which is usually considered very good __scalability__. Efficiency is a performance metric defined as *Sp/p*. It is a value, typically between zero and one, estimating how well-utilized the processors are in solving the problem, compared to how much effort is wasted in communication and synchronization. Algorithms with linear speedup and algorithms running on a single processor have an efficiency of 1, while many difficult-to-parallelize algorithms have efficiency such as 1/log *p* that approaches zero as the number of processors increases.