Also da ich hier keinen Thread zur LaufzeitAnalyse gefunden habe, packe ich den kram einfach mal hier rein.
Sei G ein Netzwerk von n Prozessoren. Jeder Prozessor in G habe höchstens d Nachbarn. Sei w weiterhin A ein konservativer, determinisstischer Routing-Algorithmus. Dann gibt es eine Permutation π für die A mindestens Ω (Wurzel(n/d)) Schritte benötigt.
Nun meine Frage: Warum ist Ω (Wurzel(n/d))?