Here's the integer multiplication algorithm that you learned back in third

grade Illustrated on a concrete example. Let's take say the numbers 1, 2, 3, 4 and

5, 6, 7, 8. As we go through this algorithm quickly,

let me remind you that our focus should be on the number of basic operations this

algorithm performs. As a function of the length of the input

numbers. Which, in this particular example, is

four digits long. So as you'll recall, we just compute one

partial product for each digit of the second number.

So we start by just multiplying 4 times the upper number 5, 6, 7, 8.

So, you know, 4 times 8 is 32, 2 carry to 3, 4 times 7 is 28, with the 3 that's 31,

write down the 1, carry the 3, and so on. When we do the next partial product, we

do a shift effectively, we add a 0 at the end, and then we just do exactly the same

thing. And so on for the final two partial

products. [SOUND] And finally, we just add

everything up. [SOUND], what you probably realized back

in third grade, is that this algorithm is what we would call correct.

That is, no matter what integers x and y you start with If you carry out this

procedure, this algorithm. And all of your intermediate computations

are done properly. Then the algorithm will eventually

terminate with the product, x times y, of the two input numbers.

You're never going to get a wrong answer. You're always going to get the actual

product. Well, you probably didn't think about was

the amount of time needed to carry out this algorithm out to its conclusion to

termination. That is the number of basic operations,

additions or multiplications of single digit numbers needed before finishing.

So let's now quickly give an informal analyses of the number of operations

required as a function of the input length n.