Komplexität

  Die Hauptkosten des Gesamtalgorithmus werden durch die Methode zur Berechnung des ggT verursacht. Während dort eine Schleife Schritte abarbeitet, stellt die Berechnung der Faktoren und jeweils nur eine einzelne Divisionsanweisung dar. Zu den Kosten des ggT sind also nur zwei Anweisungen zu Addieren, um die Gesamtkosten zu ermitteln.

Die Laufzeit dieses Algorithmus zur Berechnung des ggT wird nun primär durch die 'Qualität' des zu berechnenden Zahlenpaars bestimmt. Dagegen zeigt er sich vergleichsweise unabhängig in Bezug auf die Größe der zu berechnenden Zahlen.

 
• Kosten im besten Fall
• Kosten im schlimmsten Fall (worst case cost)
• Kosten im durchschnittlichen Fall (average cost)
• Einordnung
  • Kosten im besten Fall
  • Kosten im schlimmsten Fall (worst case cost)
  • Durchschnittliche Kosten (average cost)