Question

Recall that you may consider circuits that output strings over $\{0,1\}$, by designating several output gates.

Let's${\mathrm{add}}_{\mathrm{n}}:\{0,1{\}}^{2\mathrm{n}}\to {\{0,1\}}^{\mathrm{n}+1}$take two n bit binary integers and produce the n+1 bit sum. Show

that you can compute the${\mathrm{add}}_{\mathrm{n}}$function with$\mathrm{O}\left(\mathrm{n}\right)$size circuits.

Short answer

The problem is solved using the complexity of the add function.

It can also be understood that there is a trade-off between space and time complexity.

Step-by-step solution

Considering the add functions

Consider, $ad{d}_n:{\left\{0,1\right\}}^{2n}\to {\left\{0,1\right\}}^{n+1}$which takes two n-bit binary integers and thus produces a $n+1$bit sum.

The user needs to compute the complexity of the add function.

The speed of the circuits depends upon the gate which has been chosen. If the complexity is greater than at that time, speed should be increased.

Continuing With the Solution

From step 1, it is understood that there is a trade-off between space and time complexity. It implies that if it is taking less time than usual, speed is the more important factor.

In the case of the binary adder, input is a two-bit binary integer. Suppose there are n digits, then it is represented with the help of n lines. The summation of the two-n bit binary numbers is equal to $n+1$the bit binary number.

The sum generated by the two-n bit binary integers is a bit long, which is represented in the form of $O\left(n\right)$. Since $n+1,n+2,\dots n+n$they are represented in the form of n.

Hence, it can be said that the complexity of $ad{d}_n$function is$O\left(n\right)$ .