Kosten im schlimmsten Fall (worst case cost)

  Handelt es sich dagegen um zwei Primzahlen, so muß die Schleife mal durchlaufen werden, um doch zwangsläufig auf 1 zu terminieren. Dabei zeigt das immernoch sehr gute Verhalten einer Logarithmusfunktion. bestimmt sich also als , wobei für die Qualität des Zahlenpaars steht, für das der ggT berechnet werden soll.