O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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).

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required