Java - Big O of bit manipulation?

Question

What is the Big O of this code? I know all the lines are O(1), except for the recursion part. I'm not sure what the big O of the recursion is, I have a feeling it is still O(1) since we have no lines that are worse than O(1), but usually recursion is O(n).

Code:

public int getSum(int a, int b) {

        if (b == 0){
            return a;
        }

        if (a == 0){
            return b;
        }

        int add = a ^ b;
        int carry = (a&b) << 1;

        return getSum(add, carry);
    }

Edit: This is not homework by the way, it is to prepare myself for interviews.

Answer 1

This function is actually O(n) worst case. As discussed in the comments above, big O notation references the asymptotic upper bound of the function. The upper bound of this function in the worst case is that each of your input numbers is a max int. That means the function is called a number of times equal to the number of bits in an integer. If your integer has 32 bits, then the function runs 32 times, each time executing a series of constant operations. That makes the function O(n), where n is the size of your integer.

Answer 2

First let me quote Wikipedia:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

You ask if performance is O(n). Well, before we can answer that, what is n?

As you can see above, n is usually defined as the size of the input. Although that usually refers to the number (count) of inputs, in this case, that could be defined as the magnitude of a or b, so the question is: Does the processing time (i.e. number of recursions) increase as a is increased and/or as b is increased?

The answer is no. There is no correlation between the magnitude of a or b and the number of recursions. Sure, the number of recursions vary, but it is unrelated to size.

Whether n is a or b, you have O_min(1), O_avg(6.24), and O_max(33).

---

UPDATE

However, you can't get 33 iterations with low values of a and b. Number of iterations are limited by the bit-length of the larger input. The bit-length would be log₂(n), which gives the answer:

O(log n) where n = max(a, b)

Answer 3

When you're trying to analyze the complexity of a recursive algorithm, it often helps to find some way in which the "size" of the inputs drop over time. For example, if you're analyzing a recursive factorial implementation, then you'd probably notice that the size of the input drops by one on each call, then use that to say that there are O(n) total calls and therefore that O(n) total work is done.

This recursive function is a bit tricky to analyze because it's not at all clear what quantity is decreasing over time. The value of the first and second arguments both can increase as the function runs, which is generally not a good thing when you're using recursion!

However, there is a useful observation here. Look at the value of the second argument to the recursive function. It's recomputed each time as

b = (a & b) << 1

which has a very interesting effect: the number of 0 bits at the end of the binary representation of b increases by at least one on each function call. To see this, imagine that b ends with k 0 bits. Computing a & b will produce a number whose last k bits are zero, then shifting the result right by one step will increase the number of rightmost 0s by one.

At the same time, the algorithm will terminate when number of rightmost 0s in the binary representation of b exceeds the position of the leftmost 1 in the binary representation of a. To see why, note that we keep ANDing b with a, and as soon as the 1 bits in b get higher than the 1 bits in a the AND evaluates to 0 and the base case triggers.

Putting this together, we can see that the number of recursive calls made is bounded by the position of the highest 1 bit in the number a, since each iteration moves the 1 bits in b higher and higher and the recursion stops when those 1s move past the 1s in a.

So now the question is what that means from a big-O perspective. If you have a number n and write n in binary, the position of the highest 1 bit in n is O(log n), since the meaning of that bit grows exponentially as a function of time. Therefore, the runtime here is O(log n), where n is the maximum of the two inputs.

Answer 4

If we analyse your function, we find the following:

• If one of the two integers passed to it is a zero -> it will be invoked one time only by the return statement at the beginning.

• If the integers passed are similar even if they are not zeros -> it will be invoked one time only. That is because of the XOR or ^ which requires the two corresponding bits to be different. For example:

  (decimal)    (binary)              (decimal)    (binary)
      5     =    101                     1     =    001
      6     =    110                     1     =    001
  **********************   Whereas    *********************
      3     =    011                     0     =    000
  

• If the integers passed are not zeros and not similar -> that will take the program to the carry part and here we need to consider the following:

  1. If the two integers have no similar corresponding bits -> (a&b) will equals zero, thus the method will be invoked only one time. For example:

     (decimal)    (binary)               (decimal)    (binary)
         1     =    001                      1     =    001
         2     =    010                      3     =    011
      **********************   Whereas   *********************
         0     =    000                      1     =    001
     

  2. If (a&b) results with no zero -> here we come to the shift part << and here is the plot. If ALL the above conditions pass -> then we have a maximum of 32 bit shift and supposing that after each shift the recursion happens -> we have a maximum of 32 recursion BUT NOT always. That means it could be not the case every time (sometimes there would be no recursion as I showed above!).

---

So, I believe it's either O(1) or O(n), and if we analyse both cases we find:

• O(1) means Constant complexity, for example:

  1 invocation  : 1 second
  10 invocation : 1 second
  100 invocation: 1 second
  And so on..
  

  But that is not the case as I showed above, because every input may cause a recursion and may not! And the recursion is not the same, although the maximum is 32 but it can be between 0 to 32.

• O(n) means a Linear complexity, for example:

  1 invocation  : 1 second
  10 invocation : 10 seconds
  100 invocation: 100 seconds
  And so on..
  

I conclude The more recursion happens, The more time it takes.

Though, I'm still open to correction.