1
$\begingroup$

I have had a problem with this concept all my life so I thought I would reach out to the experts for help!

Here is the problem statement:

Quote: "Consider how much work is required to multiply two -digit numbers using the usual grade-school method. There are two phases to working out the product: multiplication and addition.

First, multiply the first number by each of the digits of the second number. For each digit in the second number this requires $n$ basic operations (multiplication of single digits) plus perhaps some "carries", so say a total of $2n$ operations for each digit in the second number. This means that the multiplication phase requires basic $n(2n)$ operations.

The addition phase requires repeatedly adding n digit numbers together a total of $(n-1)$ times. If each addition requires at most $2n$ operations (including the carries), and there are $(n-1)$ additions that must be made, it comes to a total of $(2n)(n-1)$ operations in the addition phase.

Adding these totals up gives about $4n^2$ total operations. Thus, the total number of basic operations that must be performed in multiplying two n digit numbers is in $O(n^2)$ (since the constant coefficient does not matter)."

End

Why is it $(n-1)$ and $2n?$

$\endgroup$
1
$\begingroup$

When you add two $n$ digit numbers, you have to do $n$ additions, one for each digit, but there might be a carry at each digit, so that's another $n$ operations, and there's your $2n$.

Now you have to add $n$ of these $n$-digit numbers, which means you have to do $n-1$ of these additions of pairs of numbers – right? To add two numbers, that's one addition; to add three numbers, that's two additions, and so on.

But in the end, you're going for an estimate $O(n^2)$, so it makes no difference whether you use $n-1$ or $n+1$, and no difference whether you use $2n$ or $17n$ or $n/42$.

$\endgroup$
  • $\begingroup$ Thanks. Nicely explained! With that said, the above problem multiplies n(2n). To me, that was saying that the carries were 2n alone. $\endgroup$ – Chris Harding Aug 17 '17 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.