Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I can see how adding 2 unsigned four-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?

share|improve this question
1  
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? –  Realz Slaw Nov 22 '12 at 23:44
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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