0
$\begingroup$

In my reference Page 22, Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it says that

given $x$ and $y$ are two numbers of $n$ bits long, then the sum of $x$ and $y$ is $n+1$ bits long, and assuming that each individual bit of this sum gets computed in a fixed amount of time, then the total running time for the addition algorithm is of the form $c_0+c_1n$, where $c_0$ and $c_1$ are some constants.

How the running time for obtaining $x+y$ is $c_0+c_1n$ ?

The example given in the reference is $x=53,y=35,x+y=88$, ie.,

pic

in this example what would be the values of $c_0,c_1$?


My Understanding

We can prove that the sum of three single digit numbers is at most $2$ digits. This shows that $x+y$ is $n+1$ digits, as each steps of the addition invloves at most adding three single digits numbers including the carry.

Additionally, looking at the addition algorithm, each single digit addition involves $2$ additions at most, and there are $n$ such operations, therefore total of $2n$.

$\endgroup$
1
  • $\begingroup$ Whether the implementation is done in hardware or software, the carry is preferably always added, even when zero (testing for zero adds overhead). So you can count $2$ additions every time (except at ends). In your understanding, the count is $2$ at most. $\endgroup$
    – user16034
    Jul 28, 2023 at 10:51

1 Answer 1

1
$\begingroup$

Strictly speaking, the claim is wrong, as nothing is said about the time for addition of two bits and a possible carry. This time might depend on the particular bit values and even not be the same for every bit.

Anyway, if we admit that the time does not depend on the numbers at all, it can only be a linear function of the number of bits if the computation is performed sequentially.

The total time is the time to add the two low order bits, then the time to compute the carry and add it to the sum of the next two bits, repeatedly, then the time for the last carry. Hence taking into account the limit cases,

$$t_1+(n-1)t_2+t_3$$

$\endgroup$
7
  • $\begingroup$ The text says: assuming that each individual bit of this sum gets computed in a fixed amount of time. $\endgroup$
    – Sooraj S
    Jul 28, 2023 at 17:56
  • $\begingroup$ @SoorajS: then the time is exactly $(n+1)\,t$. Note that this somehow contradicts the notation $c_0+c_1n$. $\endgroup$
    – user16034
    Jul 28, 2023 at 18:02
  • $\begingroup$ If I take $t$ the time to add individual bits, and $t'$ the time to compute carry, then there are $2n$ additions of individual bits, and there are $n$ carries to find. So isn't it $2nt+nt'$? $\endgroup$
    – Sooraj S
    Jul 28, 2023 at 18:18
  • 1
    $\begingroup$ @SoorajS: of course. Though they say it in a clumsy way. $\endgroup$
    – user16034
    Jul 28, 2023 at 18:53
  • 1
    $\begingroup$ @SoorajS: every process that handles $n$ elements in constant time has complexity $c_0+c_1n$. The text was poorly written, so that one has to conclude $c_0=c_1$, which is not realistic. $\endgroup$
    – user16034
    Jul 28, 2023 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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