11
$\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.

|cite|improve this question
$\endgroup$
17
$\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)$.

|cite|improve this answer
$\endgroup$
  • $\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
  • 1
    $\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.

|cite|improve this answer
$\endgroup$
  • 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
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?

|cite|improve this answer
$\endgroup$
  • $\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

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.