order of an operation when upper bound is fixed

Question

I recently had an interview and was asked to find number of bits in integer supplied. I had something like this:

#include <iostream>

using namespace std;
int givemCountOnes (unsigned int X) {
  int count =0;
  while (X != 0 ) {
    if(X & 1)
      count++;
   X= X>>1;
  }

 return count;

}

int main() {
cout << givemCountOnes (4);
return 0;
}

I know there are better approaches but that is not the question here.

Question is, What is the complexity of this program?

Since it goes for number of bits in the input, people say this is O(n) where n is the number of bits in input.

However I feel that since the upper bound is sizeof(unsigned int) i.e. say 64 bits, I should say order is o(1).

Am I wrong?

I am sure somebody will edit it... probably me, sooner or later. But could you try and learn to spell words properly and use punctuation correctly? — jogojapan, Jun 13 '13 at 07:52

score 5 · Answer 1 · answered Jun 13 '13 at 07:59

The complexity is O(N). The complexity rises linearly with the size of the type used (unsigned int).

The upper bound does not matter as it can be extended any time in the future. It also does not matter because there is always an upper bound (memory size, number of atoms in the universe) and then everything could be considered O(1).

fkl · Answer 2 · 2013-06-13T09:47:50.147

2

I will just add a better solution to above problem.

Use the following step in the Loop

x = x & (x-1);

This will remove the right most ON bit one at a time.

So your loop will at max run as long as there is an ON bit. Terminate when the number approaches 0.

Hence the complexity improves from O(number of bits in int) to O(number of on bits).

edited Jun 13 '13 at 09:47

answered Jun 13 '13 at 08:45

fkl

5,412
4
28
68

score 0 · Answer 3 · answered Jun 13 '13 at 07:59

The O notation is used to tell what the difference is between different values of n. In this case, n would be the number of bits, as (in your case) the number of bits will change the (relative) time it takes to perform the calculation. So O(n) is correct - a one bit integer will take 1 unit of time, a 32-bit integer will take 32 units of time, and a 64-bit integer will take 64 units of time.

Actually, your algorithm is not dependent on the actual number of bits in the number, but the number of the highest bit set in the number, but that's a different matter. However, since we're typically talking about O as the "worst case", it's still O(n), where n is the number of bits in the integer.

And I can't really think of any method that is sufficiently better than that in terms of O - I can think of methods that improve the number of iterations in the loop (e.g using a 256 entry table, and dealing with 8 bits at a time), but it's still "bigger data -> longer time". Since O(n) and O(n/2) or O(n/8) are all the same (it's just that the overall time is 1/8 in the latter case than in the first case).

I posted a slightly better algorithm. Though it still doesn't change in terms of big O. Still it is the best constant number optimization for this problem in particular with variable length integers. — fkl, Jun 13 '13 at 09:24

score 0 · Answer 4 · answered Jun 13 '13 at 08:21

0

Big O notation describes count of algorithm steps in worst case scenario. Which is in this case, when there is a 1 in the last bit. So there will be n iterations/steps when you pass n bit number as input.

Imagine a similar algorithm which searches count of 1's in a list. It's complexity is O(n), where n is a list length. By your assumption, if you always pass fixed size lists as input, then algorithm complexity will become O(1) which is incorrect. However if you fix bit length in algorithm: i.e. something like for (int i = 0; i < 64; ++i) ... then it will have O(1) complexity, since it doing O(1) operation 64 times, you can ignore constant here. Otherwise O(c*n) is O(n), O(c) is O(1), where c is constant.

Hope all these examples helped. BTW, there is O(1) solution for this, I'll post it when I remember :)

answered Jun 13 '13 at 08:21

Davit Samvelyan

198
8

The O(1) involved ANDing with constant values. However, it only works with fixed width integer values (32, 64 or 128 bits) that are predetermined. Not generically for any integer width. (Downvote is not mine). – fkl Jun 13 '13 at 08:50
It seems that someone got confused by my statement that the same algorithm for fixed length is O(1). :D – Davit Samvelyan Jun 13 '13 at 09:09
Probably :) I countered though now with a +1. The explaination was useful in my opinion. – fkl Jun 13 '13 at 09:18

score 0 · Answer 5 · answered Jun 13 '13 at 09:54

There's one thing should be cleared: the complexity of operation on your integer. It is not clear in this example, as you work on int, which is natural word size on your machine its complexity seem to be just 1.

But O-notation is about large amount of data and large tasks, say you have n bit integer, where n is about 4096 or so. In this case complexity addition, subtraction and shift are of O(n) complexity at least, so your algorithm then applied to such integer would be O(n²) complexity (n operations of O(n) complexity applied).

Direct count algorithm without shifting of whole number (in assumption that one bit test is O(1)) gives O(n log(n)) complexity (it involves up to n additions on log(n) sized integer).

But for fixed length data (which is C's int) big O analysis is simply meaningless, because it based on input data of variable length, say more, data of virtually any length upto infinity.

order of an operation when upper bound is fixed

5 Answers5