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
    Commented Sep 4, 2016 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
    Commented Sep 4, 2016 at 12:35
  • $\begingroup$ Finally, "complexity classes" and "Landau classes" are not the same thing. $\endgroup$
    – Raphael
    Commented Sep 4, 2016 at 12:36

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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