What is the space complexity of this binary addition solution?

Question

I am working on an interview problem from Facebook Software Engineer

The Problem: Write a function which given two binary numbers as strings returns the sum of them in binary

Here is my solution in Java(Tested it, It works!!!)

private static String sum(String bin1, String bin2)
{
    int dec1 = binToDec(bin1);
    int dec2 = binToDec(bin2);
    int sumTo = dec1 + dec2;
    StringBuilder bin = new StringBuilder();
    do {
        bin.append(sumTo%2);
        sumTo = sumTo/2;
    }while(sumTo > 0);

    return bin.reverse().toString();
}
private static int binToDec(String bin) 
{
    int result = 0;
    int len = bin.length();
    for(int rep = len-1; rep >= 0; rep--) {
        int multiplyBy = bin.charAt(rep) == '1' ? 1 : 0;
        result += multiplyBy * Math.pow(2, len-1-rep);
    }
    return result;
}

I am trying to analyze the time and space complexity of the sum. I know that the time complexity of my algorithm would just be O(logn) because of the binary conversion.

Like usual, I am having a hard time with space complexity. I know that the space complexity would just depend on the memory I allocated from the heap, in this case the string to represent the binary sum result

I know that String concatenation is an expensive operation because it requires copying 1 chars, then 2 chars, then finally logn chars. I know that traditional String concatenation runs in O(n²) space. Would it be the same here?

I tried doing the calculations myself

1 + 2 + 3 +.... logn-1 + logn <BR>
logn + logn-1 + ....1<BR>
 logn(logn + 1)/2

and got the final result of ^{logn(logn + 1)}⁄₂ which would be O((logn)²). Is that the right space complexity for this algorithm? Or is it just O(n²) because the two functions are in the same family?

I don't believe so. n is the decimal representation of the sum — committedandroider, Mar 30 '15 at 01:25
@committedandroider You just confirmed it. Your description for n doesn't make much sense. What do you mean by the decimal representation? Do you mean the value? Would it differ for binary representation? Or do you mean the length in digits. And why would you give the analysis for value unrelated to input? Your algorithm certainly doesn't work in logarithmic time in respect to input, precisely because of conversion, which is done in linear complexity. — luk32, Mar 30 '15 at 01:33
In this case, what would space complexity be in terms of the input(total string length)? — committedandroider, Mar 30 '15 at 02:37
as I see it `n` is number of digits (does not matter if in dec or bin in terms of complexity) so both conversions are `O(n)` time complexity resulting in `O(3*n+1)->O(n)`. for space you need to count the operands of your functions too so if they are not pointers then they need `O(n)` space per each bin string resulting in `O(4n+6) -> O(n)` space complexity. if `n` is the value then each `O(n)` will be `O(log(n))` ... still dont get it why to convert to/from dec/bin you can add in `O(n)` directly in binary very easy and use almost inplace ... need just one digit to add if overflow ... — Spektre, Mar 30 '15 at 06:53
if you count also the string reallocations then your time complexity gets `O(n^2)` and space complexity doubles which is still O(n) ... this can be also avoided ... if you allocate enough space prior to conversion ... PS it is pretty early here so If I have overlooked something correct me — Spektre, Mar 30 '15 at 06:58
@committedandroider: You're treating operations as O(1) that you really shouldn't; for example, string concatenation takes time proportional to the length of the result string. You also seem to be confused about the difference between a number and its decimal representation; you can't take the logarithm of the decimal representation of a number. Your algorithm only works when the input numbers and their sum both fit into an int, meaning n1 and n2 can't be any bigger than 31; I don't know whether this is enough, but if you're analyzing time complexity, it doesn't seem like enough. — user2357112, Aug 19 '15 at 03:21
Yeah String concatenation runs in O(n^2). Should have saw that. I changed that to use the StringBuilder class and reverse the result at the end. I agree about the restrictions on my function(not bigger than 31). A better way to go about this would be to add the individual digits and use a remainder variable. But with this implementation and using StringBuilder instead, is my analysis correct? — committedandroider, Aug 19 '15 at 04:53

score 0 · Accepted Answer · edited May 23 '17 at 11:43

After revisiting this question, I should have been more clear with my use of variables.

The time complexity of my algorithm is O(log₂m + n₁ + n₂) Big O Summation where m is the decimal representation of the sum of the binary numbers. n₁ and n₂ are the number of bits, or the length of bin1 and bin2 respectively.

For Space Complexity, you have to take into account all memory allocated by your algorithm - from the stack and the heap.

When analyzing the amount of space I've used from the stack, I noticed that I've made no recursive calls that that space would be O(1). Similarly when analyzing the amount of space I've used form the heap, it would also be O(1) because no matter the input, I always allocate the same amount of space (3 ints), using no data structures.

Therefore the space complexity of my solution is O(1)

What is the space complexity of this binary addition solution?

1 Answers1