# Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?

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))?

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.
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.