What is the time complexity of binary sum, the sum of two binary numbers done like in elementary school?

Say one number is F and his length is $s$ bits, and another number is H and his length is $t$. (Like Time complexity of binary multiplication? , but with sum).

  • 3
    $\begingroup$ Welcome to Math.SE! Does "binary sum" mean you are adding numbers represented in base two, or does it mean you are adding two numbers? Or both? It would be helpful if you could add some context to the Question, not least because it would help Answers be written at a level that is useful to you. $\endgroup$ – hardmath Dec 2 '13 at 11:37
  • 1
    $\begingroup$ @hardmath binary sum mean you are adding numbers represented in base two $\endgroup$ – ben Dec 2 '13 at 11:39

The short answer is that adding two numbers by the "elementary school" algorithm has linear complexity. That is, given binary representations F and H of respective lengths $s$ and $t$, the number of steps needed is $O(s+t)$.

This should be intuitively clear. After arranging the longer number over the shorter one, starting at the right hand side and adding-with-carry from right to left will generate a sum of length at most $\max(s,t)+1$. The computation required for each bit of the result is $O(1)$ or constant, since this merely combines the two respective bits of F and H with a possible carry from the previous step. (There are at most eight possibilities for such a step.)

  • $\begingroup$ and i have another question is like this question: if ןnstead of sum, i do mult, the time complexity will be O(s*t)? $\endgroup$ – ben Dec 2 '13 at 12:55
  • $\begingroup$ Yes, which is roughly what the earlier Question you linked to says. We might think in terms of doing the multiplication as shift-and-add, based on the bits of the shorter multiplicand, so that you need to add (at most) $s$ shifted copies of the $t$ bit length number, which amounts to $(s-1)$ additions of (at most) $s+t-1$ bit length representations. I leave it to you to verify $s*O(s+t) = O(s*t)$ when $s \le t$. $\endgroup$ – hardmath Dec 2 '13 at 13:36
  • 1
    $\begingroup$ But in math.stackexchange.com/questions/226394/… , he tell that it's O(n^2).. so who wrong? $\endgroup$ – ben Dec 2 '13 at 13:50
  • $\begingroup$ In that Question $n=s=t$, and we are just taking the large size to fit both multiplicands. The Accepted Answer there mentions using two different sizes, one of $n$ bits and one of $m$ bits. But these are exercises for you to think through! $\endgroup$ – hardmath Dec 2 '13 at 13:59
  • $\begingroup$ Can we say ,in the sum, that is O(n) too when n is the length of the bigger number? $\endgroup$ – ben Dec 2 '13 at 15:03

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.