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