How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?

Question

BACKGROUND:

Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will).

Assumption: Just for the sake of this question, let's assume that the term "basic operation" means an addition or a multiplication operation between two single-digit numbers.

Now we have to calculate the number of basic operations involved in the simple multiplication (the one we learnt in 3rd grade) of any two numbers, provided that both the numbers have the same length (i.e. the number of digits).

Let's say n represents the length of the numbers.

Let the numbers be 1234 and 5678. The following image shows the multiplication:

As you can see, each row (i.e. each partial product of the first number with a digit of the second number) involves 4 multiplication operations, and 4 addition operations (think of the carries). Depending on the number of carries (and thus depending on the original numbers), in the case of any two numbers, in each row, it could be at least 0 additions (no carry) and at most 4 additions (a carry from each digit-to-digit multiplication).

In other words, each row involves ≤ 2n operations. As there are n rows, so the basic operations in all the rows are n(2n), or 2n².

---

QUESTION:

Now comes that one final addition (shown in black pen in the image). From the video lecture

The final addition requires a comparable number of operations. Roughly, say, another at-most 2n² operations.

The question is

1. What is meant by "comparable" number of operations?

2. Now, there will be at-most n-1 _'s in the partial products, which means n-1 addition operations. Apart from those, there will be at-least n additions (if there isn't a carry from the addition of the left-most digits in the partial products), and at-most n+1 additions (if there IS a carry from the addition of the left-most digits in the partial products). This makes a total of, at-most, n-1+n+1 or 2n addition operations in this step. So why are they saying 2n²?

Answer 1

It's hard to tell what anyone means by "comparable" in a specific context. I would take it to mean "of the same order", so something like $n^2$, maybe $100\cdot n^2$ or $0.0001\cdot n^2$, but not $n$ or $n^3$.

The final addition is doing (roughly) $n$ additions of numbers of (roughly) non-$\_$ $n$ digits, and each of those additions takes (roughly) $n$ additions of single digit numbers. So that's why you end up with (roughly) $n^2$ additions.

Answer 2

Instead of collecting each partial product then adding all of them at the end, let's keep a register that is 2n digits long, initially full of zeros, and we will update it as we go.

After each n + 1 digit-long partial product, we add it into the sum register. We need to shift it one digit higher each round. We need to do n + 1 additions, then need to do more additions to cascade any carries. So there will be upper limit of 2n additions into the sum register each round. Since there are n rounds, we get a total of 2n² operations for the sum register round.

This is why it's comparable to the multiplication round, although the multiplication round is a mix of multiplication and addition while the sum register round is just additions.