# How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?

I am going through the book of Parallel Programming and a parallel algorithm is often classified as Efficient, Optimal or Suboptimal. I googled these terms but I didn't found a clear definition for them.

Define $T(n)$ as the running time of the sequential algorithm, $t(n)$ as the running time of the parallel one, $p(n)$ as the number of processing units. Hence work $w(n)=p(n)t(n)$, speedup factor $S(p)=\frac{T(n)}{t(n)}$, efficiency $E=\frac{T(n)}{p(n)t(n)}\times 100\%$.

The parallel algorithm is efficient if:

1. $t(n)=O(\log^c n)$ for some constant $c>0$; and
2. work $w(n)=T(n)O(\log^c n)$

The parallel algorithm is optimal if:

1. $t(n)=O(\log^c n)$ for some constant $c>0$; and
2. work $w(n)=O(T(n))$

Are the definitions of efficient and optimal correct? And what about suboptimal?

I am literally a noob to parallel programming and I googled a lot without a clue. Any help would be greatly appreciated. Thanks in advance.

First, it obviously holds that $w(n)=\Omega(T(n))$, since a sequential algorithm can simulate the parallel one by doing the work of all processors one by one, which takes $p(n)t(n)=w(n)$ time. Here I assumed that $T(n)$ is a lower bound on the time required for a sequencial algorithm to preform the given task. This explains your notion of optimallity, one cannot do better then $w(n)=O(T(n))$.
As for efficient, requiring the running time for each processor to be $O(\log^c n)$ results in exponential speedup over a sequencial algorithm, since $T(n)=\Omega(n)$ (the sequencial algorithm must at least read the entire input), and thus $T(n)=\Omega\left(2^{[t(n)]^{\frac{1}{c}}}\right)$.
The additional requirement of $w(n)=T(n)O(\log^c n)$ means that the overall number of operation does not increase too much (you pay in processing power for better computation time). So in this case, the overall number of operations for the sequencial/parallel algorithm is equivalent up to polylogarithmic factors.