Algorithms in a Nutshell

Parallel Algorithms

A computational process may spawn several computational processes to work simultaneously on subinstances of a problem. Using the same example from the previous section, "Offline Algorithms," it is possible to speed up the performance of n/2 Sequential Search executions by executing these searches in parallel on n processors. The resulting worst-case cost of the parallel n/2 searches is O(n). If you are interested in pursuing this idea further, you should read the book by Berman and Paul (2004) on the subject. You may also find it worthwhile to read about actual systems that take advantage of parallelism afforded by multicore processors; see Armstrong's Programming Erlang: Software for a Concurrent World (2007).