15
$\begingroup$

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.

Improve this question
$\endgroup$
19
$\begingroup$

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)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Is reading all the data theoretically necessary. For addition of any two numbers $a$ and $b, a: a \ge b, a + b \le 2a$. Calculating $2a$, can be done in $O(1)$ operation, through shifting. Appending a $0$. Consider that. Might you not find a faster estimate for the sum, refine that estimate until it's correct. In less than $n$ operations? $\endgroup$ – Tobi Alafin Dec 30 '16 at 16:04
  • 3
    $\begingroup$ Yes, it is a theoretical necessity, because: each bit of the input is used non-trivially in the output, where by non-trivial I mean it is not the identity function. In your $2a$ example, whether $2a$ can be computed in $O(1)$ time depends on the computational model: if appending a $0$ is a constant-time operation, then yes. If you have RAM access, you need $O(\log(n))$ time to write the bit's address if you already know the length of $a$, or $O(n)$ time if you have to read all of $a$ to find out. In this $2a$ example, many output bits are trivial functions of input bits. $\endgroup$ – Lieuwe Vinkhuijzen Dec 30 '16 at 17:33
  • $\begingroup$ I have an algorithm that finds the length of $a$ in $O(\log n)$. It uses binary search. $\endgroup$ – Tobi Alafin Dec 30 '16 at 17:36
  • 3
    $\begingroup$ @TobiAlafin If your model supports RAM addressing, then your binary search runs in $O(\log n)$ steps, correct. On Turing Machine, and in a text file not loaded into main memory, this takes $O(n)$ time. In either case, to answer your question, with or without RAM addressing to speed up lookup, your algorithm will have to look at all the bits of the input to compute $a+b$. Suppose that it didn't, and on an input of $42$ bits, it does not inspect the $6$-th bit. Then I could flip that bit, and it would give the wrong answer. $\endgroup$ – Lieuwe Vinkhuijzen Dec 30 '16 at 17:43
  • 2
    $\begingroup$ Basically all operations are $\Omega(n)$, for this reason. The only exception is if you are dealing with a somehow ordered data-structure: e.g. you do not have to visit a whole BST to check if it contains a certain value, but this is true only because of the invariants that come with the BST. $\endgroup$ – Bakuriu Dec 30 '16 at 21:55
7
$\begingroup$

In order for complexity analysis to make any formal sense at all, you have to specify a formal computational model within which the algorithm in object is being executed, or, at the very least, a cost model, which specifies what the basic operations are and their costs.

In most contexts, arithmetic operations are assumed to take $\Theta(1)$ time. This is usually reasonable, as we are interested in algorithmic complexity irrespectively of the numbers involved. This is called the uniform cost model.

If numbers can grow unbounded, or we are interested in analyzing the operations themselves, arithmetic operations are taken to have cost $\Theta(|x|)$, proportional to the size of input.

Now, can operations have a cost that's less than that? Possibly, however you'll have to formally define a computational model in which it can happen.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ As an additional example, a carry look-ahead adder takes, under appropriate simplifying assumptions, $\Theta(\log n)$ time to compute the sum of two $n$-bit numbers. $\endgroup$ – Fabio Somenzi Dec 30 '16 at 22:08
4
$\begingroup$

When the time complexity of a computation such as adding two $\lg n$-bit numbers $x$ and $y$ is considered, it is often assumed that the bits in $x$ and $y$ are available all at once unless the algorithm in question is bit-serial and bits of $x$ and $y$ arrive over time. So, while it is true that every bit counts and we can't ignore any given bit, one doesn't need to spend $O(\lg n)$ time to wait for bits of $x$ and $y$ to arrive before the computation begins or in-between the successive bit additions. With this convention in place, $x$ and $y$ can be added using a Brent-Kung prefix adder in $O(\lg\lg n)$ time complexity using constant fan-in and constant-fan-out gates. Brent-Kung uses a particular prefix gate with two inputs and two outputs and $O(1)$ gate delay to achieve this time complexity.

One other point is that time and space complexities of an algorithm or computation cannot not be expressed in terms of implementation specific figures such as address or data bus widths, RAM or register size (number of bits, bytes, words), clock rates, etc of a particular physical system made out of a constant number of components. Such complexities involve variables such as $n,\lg n,$ etc, whereas an implementation of an algorithm on a specific piece of hardware or system can be determined down to a nanosecond if all system and component time and space values are accurately predictable. As far as time and space complexities are concerned, all physical systems built out of a constant number of components have $O(1)$ time and $O(1)$ space complexity.

The classic references on this sort of question are:

(1) Winograd, Shmuel. "On the time required to perform addition." Journal of the ACM (JACM) 12.2 (1965): 277-285.

(2) Brent, Richard P., and Hsiang T. Kung. "A regular layout for parallel adders." IEEE transactions on Computers 3 (1982): 260-264.

The $O(\lg \lg n)$ time complexity of B-K prefix adder is consistent with Winograd's lower bound given in [1].

Improve this answer
$\endgroup$
3
$\begingroup$

The input to addition is two arbitrary numbers. Since they are arbitrary, you must read each bit, and therefore the algorithm is $\Omega(n)$.

Imagine your algorithm successfully adds 1010100110 and 0010010110 without reading each bit. In order for you algorithm to be able to add arbitrary inputs, I should be able to randomly flip any one of these bits, and the algorithm still output a correct (but different) addition. But if your algorithm doesn't read every bit, how could it tell that the flipped input was any different than the original input?

Improve this answer
$\endgroup$
2
  • $\begingroup$ What I was thinking if was a means to approximate the sum in less than $n$ operations. $\endgroup$ – Tobi Alafin Dec 30 '16 at 19:45
  • $\begingroup$ Absolutely. You just have to define what "approximate" means in your algorithm. Depending on that definition, adding the two most significant bits could be an approximate sum, which could be done in o(n) time. When you mention the "addition" algorithm, I think we all take that to mean the answer must be exact. $\endgroup$ – murrdpirate Dec 30 '16 at 20:07
0
$\begingroup$

To extend on other answers: When we are interested in average-case time complexity, it is possible to get an addition algorithm that adds in $\log n$ steps in the average case (assuming certain bitwise operations are $O(1)$), see [1] and [2]. And modern computer architectures add in parallel, so the number of steps to add two $n$-bit numbers using a hardware adder is almost always better than $O(n)$, assuming we have polynomially many processors; see AYO's answer, for example.

[1]: Richard Beigel, William Gasarch, Ming Li, and Louxin Zhang. "Addition in $\log_2 n+O(1)$ Steps on Average: A Simple Analysis"

[2]: G. Schay, "How to add fast–on average". American Mathematical Monthly, 102:8 (1995), 725-730.

Improve this answer
$\endgroup$

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.