Optimal Parallel Algorithms
Optimal Parallel Algorithms
- NC -- The class of algorithms that run in Q(logmn) time using Q(nk) processors
- General Boolean Functions Cannot be Computed any Faster than Q(lg n)
- Q(lg n) is optimal for computing the sum of n integers