Number of Basic Operations - Grade School Multiplication Algorithm 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!
 A: 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$
A: @HelloWorld
I am too late to answer this question.
Imagine a calculator. When you say 2+3 in a calculator, it is a single instruction. Similarly, 2*3 is also an instruction. So, every operation is an instruction to CPU, whether it may be sum or multiplication or division. In UG%, while working on 8086 processor, I saw vividly how every operation (instruction), a processor performs. You can also, spend some time on any processors.  
In our case, algorithms care about these instructions, because every basic operation we perform in this algorithm is taken as an instruction by CPU. We are here to calculate the maximum number of basic operations (instruction) our CPU needs to perform for producing this partial product 4*5678. 
5678
*1234
Lets see the instructions of a CPU, for our algorithm (only partial product):
4*5678


*

*4*8--->32, HOLD 2 & CARRY 3

*4*7--->28, 

*28+3-->31, HOLD 1 & CARRY 3

*4*6--->24

*24+3-->27, HOLD 7 & CARRY 2

*4*5--->20

*20+2-->22, HOLD 2 & CARRY 2

*2 & 2 -->22712


If you observe, 2, 7, 1, & 2 are values we (CPU) held. But, we ignore the last 2 of 22, comes from CARRY 2. Remember the CARRY elements are 3, 3, 2, 2. Generally, we assume 3, 3, 2 and ignore 2. 
2233 (carry elements)
 5678
  *4
------>
22712 
So, value of the partial product is 22712---basic number of operations required for this 8 which is <=2n. No, it is not 7.
<=2n, which is, in any given case, what ever value 'n' holds, the worst possible operations required (instructions) for producing this output (partial product) is always <=2n!!
