3

I wrote a program that computes the largest power of 2 in a given input number. For instance, the largest power of 2 in the number 26 is 16, since 24 is 16. Here is the algorithm:

uint power2( uint n )
{
   uint i = n;
   uint j = i & (i - 1);
   while( j != 0 )
   {
      i = j;
      j = i & (i - 1);
   }
   return i;
}

I've struggled a bit with analysis of algorithms. I know we are trying to figure out the Big-Oh, Big-Omega, or Big-Theta notation. In order to analyze an algorithm, we are supposed to count the number of basic operations? My problem here is that I see two lines that could be basic operations. I see the line uint j = i & (i - 1) outside the while loop and I also see the j = i & (i - 1) inside the while loop. I feel like the one inside the while loop is a basic operation for sure, but what about the one outside the while loop?

The other part I struggle with is determining how many times the body of the while loop will execute. For instance, if we have a for loop for(int i = 0; i < n; i++) {...} we know that this loop will execute n times. Or even in a while loop while(i < n * n) {... i++} we know this loop will run n * n times. But for this while loop, it varies depending on the input. For instance, if the number you pass into it is a power of 2 right off the bat, the while loop will never execute. But, if you pass in a really large number, it'll execute many times. I don't know how many times it will execute to be quite honest. That's what I am trying to figure out. Can anyone help me understand what is going on in this algorithm and the number of times it runs, like O(n) or O(n^2), etc?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
GenericUser01
  • 337
  • 3
  • 11
  • 27

1 Answers1

9

This is a good example of an algorithm where it's easier to reason about it when you have a good intuitive understanding of what it's doing rather than just by looking at the code itself.

For starters, what does i & (i - 1) do? If you take a number written in binary and subtract one from it, it has the effect of

  • clearing the least-significant 1 bit, and
  • setting all the bits after that to 1.

For example, if we take the binary number 1001000 (72) and subtract one, we get 1000111 (71). Notice how the least-significant 1 bit was cleared and all the bits below that were set to 1.

What happens when you AND a number i with the number i - 1? Well, All the bits above the least-significant 1 bit in both i and i - 1 are unchanged, but i and i - 1 disagree in all positions at or below the least-significant 1 bit in i. This means that i & (i - 1) has the effect of clearing the lowest 1 bit in the number i.

So let's go back to the code. Notice that each iteration of the while loop uses this technique to clear a bit from the number j. This means that the number of iterations of the while loop is directly proportional to the number of 1 bits set in the number n. Therefore, if we let b represent the number of 1 bits set in n, then the runtime of this algorithm is Θ(b).

To get a sense for the best and worst-case behavior of this algorithm, as you noted, if n is a perfect power of two, then the runtime is O(1). That's as good as this is going to get. For the worst case, the number n could be all 1 bits, in which case there will be Θ(log n) 1 bits set in the number n (since, in binary, the number n requires Θ(log n) bits to write out). Therefore, the worst-case runtime is Θ(log n).

In summary, we see that

  • the best-case runtime is O(1),
  • the worst-case runtime is Θ(log n), and
  • the exact runtime is Θ(b), where b is the number of bits set in n.
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • if this doesnt get an A grade then I dont know what will :-) – pm100 Feb 07 '16 at 19:21
  • I understand now about the best-case runtime being O(1), but I am still confused on the worst-case being Θ(log n). How did you know it was log n? – GenericUser01 Feb 07 '16 at 19:22
  • 1
    @GenericUser01 We know that the runtime of the inner loop is directly proportional to the number of 1 bits set in the number. Therefore, if we pick a number with every bit set to 1, then the runtime will be as large as possible for a given number of bits. The reason we get the log term here is that the binary number 111...11 (k times) represents the number 2^0 + 2^1 + 2^2 + ... + 2^k = 2^{k+1} - 1. Therefore, a number with k bits set is of size roughly O(2^k), meaning that the size of n is exponentially larger than the number of bits set. Inverting the exponent gives the log term. – templatetypedef Feb 07 '16 at 19:24
  • @GenericUser01 Generally speaking, any algorithm that does O(1) work for each digit or bit in a number [will have time complexity O(log n)](http://stackoverflow.com/questions/9152890/what-would-cause-an-algorithm-to-have-olog-n-complexity/9153420#9153420), where n is the number in question. – templatetypedef Feb 07 '16 at 19:25
  • @templatetypedef Why do we need to invert O(2^k)? How come that isn't the Big-Oh of the algorithm? I understand that the runtime depends on the number of bits set to `1`. I'm still just having a hard time seeing how this is log n. I checked out the other link and the example of dividing by 2 until you get a digit less than or equal to 1 makes sense, but here it's a bit more difficult for me to see. – GenericUser01 Feb 07 '16 at 19:45
  • @GenericUser01 This is a great spot to try out some examples by hand and see if you notice a pattern. Convert the numbers 1, 11, 111, 1111, 11111, and 111111 into decimal from binary. What numbers do you get back as a result? You should notice that you have to roughly double each number to get the next one, which means that you have to roughly double the size of n to increase the number of bits in n. This gives a good intuition for why the number n has roughly log n bits in it. Since we care about the number of bits in n, the runtime is O(log n). – templatetypedef Feb 07 '16 at 19:50
  • Something I noticed. Wouldn't our best case running time be Big-Omega of (1)? 1 is the best our program can do and the worst our program will do is log n. So wouldn't this be in Big-Omega(1) and Big-Oh(log n)? – GenericUser01 Feb 09 '16 at 20:48
  • @GenericUser01 It would not be wrong to say that the runtime of the function on any input is Ω(1) and O(log n), though that's a bit less precise than the bound of Θ(b), where b is the number of bits set. – templatetypedef Feb 09 '16 at 21:34
  • I talked with my professor and asked about it being Ω(1), O(log g), and Θ(b) where b is the number of bits set and he said I am very close. What is $n$ in this algorithm? – GenericUser01 Feb 10 '16 at 02:33
  • n is the number provided as input to the function. – templatetypedef Feb 10 '16 at 04:09
  • For the algorithm, n isn't the size of the input, but rather it IS the input. So in that case the input size if the number of bits required to encode n, or rather, the magnitude of n: |n|. So would this big Big-Theta( |n| )? In other words, is |n| the same as b? – GenericUser01 Feb 10 '16 at 04:43
  • I think you're mixing up two independent concepts. In the code you've written, the variable n is the actual argument to the function, so if you want to reason about the time complexity of the code in terms of n, you'd be talking about the number n itself. On the other hand, time complexity is officially defined in terms of the number of input bits needed to represent the input, so as a function of the number of bits N in the number n, the runtime is O(N). However, I'd consider it an abuse of notation to use n to refer both to the number of bits in the input and the numeric value. – templatetypedef Feb 10 '16 at 05:23
  • Also, remember that the runtime is not Theta(the number of bits in n). It only depends on the number of 1 bits. – templatetypedef Feb 10 '16 at 05:24
  • I am just confused on what is Big-Oh, Big-Omega, and Big-Theta then. It makes sense that Big-Omega is 1 since that is out best possible running time and that Big-Oh is log n which is our worst running time. I don't see why it couldn't be Big-Theta of |n|. I know its supposed to be the number of bits in n. We're not reasoning about the time complexity. We are reasoning about the number of basic operations performed. – GenericUser01 Feb 10 '16 at 06:07
  • My reasoning is that the number of basic operations performed is Big-Theta(the number of bits in n). For instance, if a power of two is entered say 2 (010), 4 (0100), or 8 (01000) then the number is bits in n is 1, however a number like 15 (001111) performs 4 basic operations since the number of bits is 4. – GenericUser01 Feb 10 '16 at 06:20
  • The number of bits in a number is not the same as the number of 1 bits. For example, there's the same number of operations performed on the binary numbers 10000000000000000000 and 1, even though there are a wildly different number of bits. This is why in my answer I used the number b to refer to the number of 1 bits set in n and said the runtime is Theta(b). – templatetypedef Feb 10 '16 at 06:29