A Recurrence Relation

We want to know the number of iterations (now recursive calls) it takes to multiply a and b. We can figure this out fairly directly from the recursive expression of the algorithm. Let T(a) be the number of iterations of Russian when run on input a.

(Aside: why isn't b needed here?)

We can argue:

• If a=1, T(a) = 1,
• If a>1 and a is odd, T(a) = 1+T((a-1)/2),
• If a>1 and a is even, T(a) = 1+T(a/2).

Now, it is a simple matter to prove by induction that $T(a) = 1+ \lfloor \log(a) \rfloor$.