1
$\begingroup$

I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are the lengths of the input strings a and b, respectively.

From my understanding, the worst case scenario is that each column in the addition will result in a carry, and since there are max(N, M) columns, the time complexity should be O(max(N, M))?

$\endgroup$

2 Answers 2

1
$\begingroup$

If $m,n>=0$, then $\max(m,n)<=m+n<=2\max(m,n)$.

So $O(\max (m,n))$ and $O(m+n)$ are the same; the two expressions are within a constant factor of each other.

$\endgroup$
3
$\begingroup$

Note that, when we compute binary addition of two binary strings $|A|=n,|B|=m$, we read $n+m$ bits. On the other hand the time complexity of computing the addition of two bits, are $\mathcal{O}(1)$, so we do $n+m$ additions that each of them needs $\mathcal{O}(1)$ time. As a result, the time complexity is $$\mathcal{O}(n+m).$$

Remember that, $A+B$ need at most $\max\{m,n\}+1$ bits space.

$\endgroup$

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.