Number of operations in total

Question

Consider the multiplication problem: $1234 \times 5432$. Using the "method taught in school", how many operations are carried out in this product?

If there are $n$ rows in the long multiplication, why are there $\leq 2n$ operations for each row? Why is the total number of operations $\leq Cn^2$ where $C$ is a constant?

I though in each row we are adding it to all the other rows. So wouldn't it be $n!$ for the first row, $(n-1)!$ for the second row etc.?

Do you know the "method taught in school"? If so, then what is your reason for asking this question? Do the calculation yourself. — Zev Chonoles, Jul 12 '13 at 17:11
How "atomic" are the operations you're looking for? That is, do you count $1+2+3$ as one operation, or two? — rurouniwallace, Jul 12 '13 at 17:12
@ZevChonoles: The reason is to quantify how many total operations are required for long multiplication. — geur, Jul 12 '13 at 17:12
@ZevChonoles: There is no distinction between "you" and "me". We are all the same (this community represents a single entity). — geur, Jul 12 '13 at 17:16
@geur: Teachers who want their students to do their own homework would disagree with that. — Zev Chonoles, Jul 12 '13 at 17:22
@geur: Now that you have demonstrated some thought / effort on the problem, I no longer object to your question. — Zev Chonoles, Jul 12 '13 at 17:24

score 0 · Answer 1 · answered Jul 12 '13 at 17:19

0

You basically create a matrix of the size O(n²), whose values you need to sum afterwards. Hence the O(n²). It's O(n) for each row because you touch each value exactly once.

answered Jul 12 '13 at 17:19

kutschkem

371

Number of operations in total

1 Answers1