3
$\begingroup$

I can see how adding 2 unsigned $n$-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in polynomial time ($O(n^2)$) via the algorithm we all learned in grade school.

However, how can we add up or multiply say $i$ numbers together in polynomial time? After we add up 2 numbers together, we get a bigger number that will require more bits to represent. Same with multiplication.

How can we ensure that these extra bits do not produce exponential blowup?

$\endgroup$
  • 1
    $\begingroup$ Multiplying $i$ numbers of size $\mathcal O (n)$ size will result in $\mathcal O(n\cdot i)$ sized number, not exponential. I think it will also take $\mathcal O\left(i \cdot M\left(n\cdot i\right)\right)$ time multiplying them in series and accumulating the result, where $M\left(x\right)$ is the cost of multiplying $x$-bit numbers. This is still polynomial time. So am I misunderstanding your question? $\endgroup$ – Realz Slaw Nov 22 '12 at 23:44
5
$\begingroup$

From what you said, I suppose that you consider complexity in terms of number of bits of the input.

Say you add up two numbers $a$ and $b$, with respectively $n_1$ and $n_2$ bits, then the result is at most $\max(n_1, n_2) + 1$ bits since $a + b \leq 2 \times \max(a, b)$.

For the multiplication, the result is at most $2 \times \max(n_1, n_2)$ bits since $a \times b \leq \max(a, b)^2$.

The important thing is that the number of bits necessary to represent the sum / product of two numbers is polynomial in the number of bits to represent those numbers. Hence, for $i$ numbers, the number of bits necessary to represent the answer is still polynomial in the number of bits of the input (since composition of polynomial functions yields polynomial functions).

Edit: actually, the really important thing is that $i$ is not part of the input, it is fixed. Otherwise, if you take for instance $2 \times 2 \times \ldots \times 2 = 2^i$, the answer takes $2^{i-1}$ bits, while the input takes $i + \log i$ bits. But if $i$ is fixed, then $2^{i-1}$ is a constant. This kind of distinction happens quite often in computer science, especially in the field of fixed parameter tractability.

$\endgroup$
  • $\begingroup$ Actually, the result of multiplication is at most $n_{1}+n_{2}$ bits, which is critically important if you're multiplying $n$ numbers but know they are all $O(1)$ bits... $\endgroup$ – Periata Breatta Feb 8 '17 at 17:56

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.