We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way?
Motivation:
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?
Note:
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– Raphael2016年09月04日 12:27:48 +00:00Commented 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– Raphael2016年09月04日 12:35:59 +00:00Commented Sep 4, 2016 at 12:35
-
$\begingroup$ Finally, "complexity classes" and "Landau classes" are not the same thing. $\endgroup$Raphael– Raphael2016年09月04日 12:36:57 +00:00Commented 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.
Explore related questions
See similar questions with these tags.