- For the input and , we define . Observe that after in each recursive call, this quantity deceases strictly. So, it is enough to prove the algorithm by induction on , which is easy.
- Two observations
- there is at most recursive calls.
- each recursive call is either terminal or leads to another recursive call plus at most 3 operations in : multiplication by 2, division by , subtraction. Each of these operations in amounts to a number of word-operations which is linear in the size of the arguments.

- Algorithm in
:
`==`

1**if****then****return**

2**if****and****then****return**

3**if****and****then****return**

3**if****and****then****return**

4**if****then****return****else****return**

*
*

2008-03-18