Общий анализ сложности параллельного алгоритма Прима для нахождения минимального охватывающего дерева дает идеальные показатели эффективности параллельных вычислений: 
 

общее время выполнения параллельного алгоритма Прима составляет: