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:
- $t(n)=O(\log^c n)$ for some constant $c>0$; and
- work $w(n)=T(n)O(\log^c n)$
The parallel algorithm is optimal if:
- $t(n)=O(\log^c n)$ for some constant $c>0$; and
- 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.