For the input
, 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.
there is at most
each recursive call is either terminal or
leads to another recursive call plus at most 3 operations in
multiplication by 2, division by
Each of these operations in
amounts to a
number of word-operations which is linear in the size of the arguments.
Therefore, the algorithm runs in