We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way?


A sequential algorithm may be O(n7) but its parallel implementation might make it O(1) so what is the motivation and tradeoff between spending time to design lower complexity algorithms then simply paralyzing it to achieve an even better performance? How this fact could be incorporated in the complexity theory notations?


Writing a parallel version is also a challenge but many times its a low hanging fruit which can be quickly solved without much creativity.

  • $\begingroup$ "but its parallel implementation might make it O(1)" -- in which model? $\endgroup$ – Raphael Sep 4 '16 at 12:27
  • $\begingroup$ Note that parallel and concurrent computing are very different things. You should clarify what you want to talk about. $\endgroup$ – Raphael Sep 4 '16 at 12:35
  • $\begingroup$ Finally, "complexity classes" and "Landau classes" are not the same thing. $\endgroup$ – Raphael Sep 4 '16 at 12:36

Parallel complexity uses the same Landau notation but a different machine model, usually the PRAM which allows polynomially many processors (in the input size). This gives rise to complexity classes like NC.

If you are into algorithms outside of massively-parallel settings, this is all quite useless: the existence of PRAM algorithms does not tell you anything about algorithms on "real" computers, i.e. such with finitely many processors.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.