2
$\begingroup$

I was readingTime complexity, it says that addition and multiplication are done in polynomial time without any explanations. Can somebody give a detailed proof why this is the case?

Thank you

$\endgroup$

closed as off-topic by Paul Frost, nmasanta, Feng Shao, Daniele Tampieri, Ernie060 Sep 18 at 7:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Paul Frost, Daniele Tampieri, Ernie060
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ In your title it seems you do not know what "polynomial time" means. (Steven answered that) In the body it seems you know that, but want a proof that addition and multiplication satisfy it. (Roddy answered that) $\endgroup$ – GEdgar Sep 17 at 12:21
3
$\begingroup$

It means that the steps you need to solve a problem (and thus the amount of time you need) is some polynomial function of its size:

$ S = f(N) $

Polynomial functions are functions that involves $N$ or $N^2$ or $N$ to other powers, like:

$5N^8+2N^5+10N^2+..$ But important, it's not exponential functions like $ 2^N$

Because that makes the amount of steps you need to solve a problem very big very quickly.

Typical problems are multiplication and mazes.

In contrast, consider the travelling sales man problem: https://en.wikipedia.org/wiki/Travelling_salesman_problem The steps to solve this problem (finding the optimal route) is not a polynomial function of the amount of cities (size).

$\endgroup$
  • $\begingroup$ This would be a much better answer if you explained what "steps" and "size" are. $\endgroup$ – Federico Poloni Sep 17 at 20:32
  • $\begingroup$ Thanks for the tip @Federico Poloni $\endgroup$ – Steven31415 Sep 17 at 20:43
2
$\begingroup$

Let us consider two numbers $a,b$ consisting of $N$ digits, that is: $$a = a_Na_{N-1}....a_1 \\ b = b_{N}b_{N-1}...b_1.$$

How can we compute $c=a+b$? Well, we need to add the digits together: $$c_1 = a_1 + b_1 \text{ mod } 10 \\ c_2 = a_2 + b_2 + r_2 \text{ mod } 10 \\ ... \\ c_{N+1} = r_{N+1}.$$

Where I define the $r_n$ as the carryover of the previous calculation (so $r_n = \left(a_{n-1}+b_{n-1} - c_{n-1}\right)/10$).

If we assume that adding two digits together $\mathcal{O}\left(1\right)$ time (so we count time in however long it takes us to add digits) - can you figure out how many of these calculations we need to do in the worst case?

After you know how many, how does this number scale with $N$? Similar decomposition in terms of digits can be used to understand the scaling of multiplication too.

$\endgroup$
1
$\begingroup$

To add, it suffices to read & add the facing digits once from least to most significant, with possible carries. As these operations take constant time, addition is performed in linear time wrt the number of digits. This is optimal.

To multiply, you multiply & add the multiplicand as many times as there are digits in the multiplier. Hence quadratic time. This is suboptimal.


To add, you can increment the addend as many times as the value of the adder. This takes time exponential in the number of digits.

To multiply, you add the multiplicand as many times as the value of the multiplier. This also takes exponential time.


On a processor ALU, additions and multiplications both take constant time.

$\endgroup$
  • $\begingroup$ karatsuba style would take linear to the number of groups in a numbers based on your own logic. $\endgroup$ – Roddy MacPhee Sep 17 at 20:06
  • $\begingroup$ @RoddyMacPhee: didn't you notice that there are three different logics ? $\endgroup$ – Yves Daoust Sep 17 at 20:08
  • $\begingroup$ optimization theory is not time complexity. I don't care. $\endgroup$ – Roddy MacPhee Sep 17 at 20:15
0
$\begingroup$

Let's first assume a machine or person that does multiplication of digits just as fast as they can add them. then we have $n$ digit multiplies for each of $n$ digits when multiplying 2 n digit numbers, and we have roughly the same number of adds, and a few more carries that don't mean much. This means we have roughly $2n^2$ multiplies and adds the factor of two will be dwarfed by n as it grows meaning it won't exceed $n^3$ for long ( in fact not past $n=2$) and so it can basically be forgotten. Each operation takes the same amount of time, implying about as fast as we can do $n^2$ of these operations we can figure out multiplying two $n$ digit numbers. $n^2$ is a polynomial; Therefore, this is an example of polynomial time.

$\endgroup$

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