# Todai Entrance Exam: Subject 2015 – Problem 3

**(1)**

**(2)**

**(3)**

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.

**(4)**

If we continue that loop, eventually one of the function parameters will be zero. So:

**(5)**

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.