patternMajorCanonical
Time complexity of addition
Viewed 0 times
additioncomplexitytime
Problem
Wikipedia lists the time complexity of addition as $n$, where $n$ is the number of bits.
Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known algorithm. I want to know, because the complexity of addition, underscores all other arithmetic operations and all algorithms which use them.
Is it theoretically impossible, to get an addition algorithm that runs in $o(n)$? Or are we bound to linear complexity for addition.
Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known algorithm. I want to know, because the complexity of addition, underscores all other arithmetic operations and all algorithms which use them.
Is it theoretically impossible, to get an addition algorithm that runs in $o(n)$? Or are we bound to linear complexity for addition.
Solution
If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (stored for example in 8MB text files). Of course, addition can be done very quickly compared to the value of the numbers; it runs in $\mathcal{O}(\log(N))$ time, if $N$ is the value of the sum.
This does not mean you can speed things up a little; if your processor handles 32 bits each operation, then you use $\frac{n}{32}$ time, but that is still $\mathcal{O}(n)$ and not $o(n)$.
This does not mean you can speed things up a little; if your processor handles 32 bits each operation, then you use $\frac{n}{32}$ time, but that is still $\mathcal{O}(n)$ and not $o(n)$.
Context
StackExchange Computer Science Q#68053, answer score: 20
Revisions (0)
No revisions yet.