We see that and with and . After each iteration, decreases by as:
So the algorithm in (2) will eventually terminate as is still the same while keep decreasing after each iteration.
If we continue that loop, eventually one of the function parameters will be zero. So:
The upper bound of number of times that a function remainder is called inside the while-loop during the calculation of is . It is easy to see from that after one iteration is less than one degree (remember , and one iteration later is less than one degree, and this pattern will keep up until one of the inputs are (degree ), that is after iterations.
Note: I’m not sure if I’m correct. Reference for the worst-case scenario in real number.