Review

We saw two multiplication algorithms for $a \times b$.

• ``Naive'' implemented multiplication by successive addition. Running time appears linear in a.
• ``Russian'' implemented multiplication by a base-2 version of the standard grade school multiplication algorithm. Running time appears logarithmic in a.

Today we'll analyze the algorithm formally.