Let a and b be two numbers of at most n decimal digits (assume for simplicity that n is a power of 2). Assume that multiplying or adding two numbers between 0 and 9 takes a computation step.

Describe the grade school algorithm to multiply a and b and show that it requires O(n^2) steps;

Describe a different algorithm with an asymptotically faster running time.

Note: As a different algorithm you can use master method. And compare the running time its faster or not.