Um algoritmo paralelo é ótimo se o seu custo estiver na mesma classe de complexidade do algoritmo sequencial ótimo.

O speedup de um algoritmo paralelo é dado pela razão entre o tempo do algoritmo sequencial correspondente, utilizando apenas um processador, pelo tempo do algoritmo paralelo, utilizando P processadores. A eficiência é calculada pela razão entre o número de processadores e o speedup.

Considerando a Taxonomia de Flynn para arquiteturas (SISD- Single Instruction Single Data; SIMD - Single Instruction Multiple Data; MISD - Multiple Instruction Single Data; e MIMD Multiple Instruction Multiple Data), pode-se afirmar que as Graphics processing units (GPUs) podem ser consideradas MISD.

A Lei de Amdhal estabelece que pequenas frações de código sequencial em um algoritmo paralelo limitam pouco seu speedup.