סיבוכיות זמן ומקום

סיבוכיות זמן:

• גרסת סריקת הקשתות כאן היא O(V * E): יש V-1 סבבים, ובכל אחד מהם נסרקות כל E הקשתות. עם ערימה בינארית ורשימות שכנות, Prim פועל בסיבוכיות O((V + E) log V).

סיבוכיות מקום:

• O(V) עבור המערך inTree (בנוסף לקשתות הקלט).

סיכום:

• Prim מרחיב עץ אחד, ומוסיף תמיד את הקשת הזולה ביותר היוצאת ממנו, עד שכל הקודקודים נכללים בו.
• הוא מפיק את אותו משקל כולל מינימלי כמו Kruskal, באמצעות אסטרטגיה שונה.