[Math] Number of Basic Operations – Grade School Multiplication Algorithm

algorithms

I am currently taking an online course and am confused by this question regarding the Number of Basic Operations.

Problem: Count the number of these basic operations performed as a function of the number n of digits in the input 

Input: Two n-digit numbers (The size of the input is the number of digits in the numbers.)
Output: the product of x * y
Basic Operation: Add or Multiply 2 Single-Digit Numbers

Example:

  5678
x 1234
--------
  22712 <= 2n Operations(Per Row)
 170340
1135600
5678000
--------- n Rows
7006652

Final Answer 2n^2

For the first line where 4 is being multiplied by each number in (5678) I count 4 operations:

1) 4*8
2) 4*7
3) 4*6
4) 4*5

So if n is the digits. N=4.

Now 2n = 8 — which doesn't make any sense to me. Shouldn't it just be n?

So for each line the operation is suppose to be 2n Operations. What does this exactly mean.
Is n=4 (since the amount of digits in the number is 4?)If n is 4 the total amount of basic operations for this would be (32). This doesn't make much sense to me.

I understand if we are taking the 4 in 1234 and multiplying it by each digit in 5678 we are performing 4 operations. Why are we making that 2n? Is it because we are multiplying 5678 by 4 so they are also included in the total amount of operations? In my mind this seems like we are 'counting' operations twice and only performing them 1x.

If anyone can help clear up some of my thoughts I'd really appreciate it. Thanks!

Best Answer

Yes, $n$ is the number of digits. In each row, you are multiplying a single digit (for the first row, the $4$) by the $n$ digits of the other number (the $5678$). You also have to do additions for the carries. In fact, you know there are no more than $n-2$ of these-there is no carry into the ones place and no product for the last carry to add to, but we can ignore the $2$ when compared with $n$. That is where each row costs $2n$ operations. Then since you have $n$ rows, to fill in all the rows above the final sum takes $2n^2$ operations. They have ignored all the additions that are required for the final product. For each row (after the first) you might have $n+1$ (consider it $n$) digits to add and as many as $n-1$ (consider it $n$) carries, for $2n$ operations. With $n-1$ (consider $n$) rows to add, that is another $2n^2$ operations, for a total of $4n^2$

Related Question