Here are the key points regarding sequential and parallel computational complexity:
Sequential computational complexity:
Refers to the amount of time required to solve a problem on a single processor using a sequential algorithm.
The time required to solve the problem increases with the size of the problem.
The most commonly used measure of sequential computational complexity is the “Big O” notation
Assumes only one processor is available to solve the problem.
Parallel computational complexity:
Refers to the amount of time required to solve a problem using a parallel algorithm on multiple processors.
The time required to solve the problem decreases as more processors are added.
The most commonly used measure of parallel computational complexity is the “Parallel Random Access Machine” (PRAM) model.
Takes into account the number of processors used to solve the problem.
Designed to reduce the computational complexity of a problem by distributing the workload among multiple processors.
Requires careful consideration of the communication and synchronization overheads associated with parallel processing.