1

There are 2 ways to compute the number of set bits in an integer, n, that I will illustrate below. There's also an O(1) way that's platform dependent, but that's not relevant for this question.

The 2 ways are:

int count = 0;
while(n)
{
  count++;
  n &= n - 1;
}

int count = 0;
while(n)
{
  if(n & 1) count++;
  n >>= 1;
}

For any 32-bit integer, both loops will execute a maximum of 32 times, where each loop does O(1) work. So this sounds like the algorithm runs in O(1) time in the domain of 32-bit integers. But we can also phrase this as the number of loops is equal to log(n), which is bounded by 32, but this phrasing suggests the algorithm is dependent on the input, and runs in O(log n) time, but the upper bound is still a constant.

Is it more correct to say that these algorithms run in O(1) or O(log n) time?

24n8
  • 1,898
  • 1
  • 12
  • 25
  • @JeffHolt Yes. Sorry. Fixed now – 24n8 Mar 16 '20 at 17:20
  • With respect to the second one, when n equals 0x100000, count will be 21. Is that what you want? – Jeff Holt Mar 16 '20 at 17:21
  • 3
    If you limit the size of inputs to a bounded range, then it makes absolutely no sense to talk about big-O classes. Big-O is an asymptotic property for the input length going to infinity. – walnut Mar 16 '20 at 17:23
  • @JeffHolt. Had another typo in it. I fixed it now by including the if statement. – 24n8 Mar 16 '20 at 17:23
  • I think your most recent edit to the second one guarantees count will always be 0. – Jeff Holt Mar 16 '20 at 17:25
  • @walnut, so Wikipedia defines "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." That doesn't seem to suggest the input always had to go to infinity, but rather we can fix it at a certain number, such as `INT_MAX` for this case? – 24n8 Mar 16 '20 at 17:26
  • I think you need to work on correctness before thinking about time. See [here](https://stackoverflow.com/q/109023/1707353). – Jeff Holt Mar 16 '20 at 17:27
  • @JeffHolt These are just typos. The question still stands. – 24n8 Mar 16 '20 at 17:29
  • @Iamanon That is correct, I didn't use the general definition. The point is that it is not useful for time complexity except at infinity. Time complexity is always a function with discrete support and positive values. That means that if you take the limit to a finite value, the result is *always* `Theta(1)` for time complexities. Considering asymptotic notation towards finite values makes more sense for functions with continuous support. – walnut Mar 16 '20 at 17:38

2 Answers2

4

None of these are O(1). You are putting a restriction on the size of input when you say the upper bound is fixed. There are numbers much bigger than 32 bits.

The time taken for the algorithm to compute the output is directly proportional to the size of the input i.e. n

An example of O(1) algo is sum of first n positive integers i.e. n*(n+1)/2

Here even if n gets bigger, the number of computation required stays constant - and thus O(1).

dreamcrash
  • 47,137
  • 25
  • 94
  • 117
Gaurav Agarwal
  • 611
  • 6
  • 18
  • 1
    `n` is an integer, so the algorithm should be proportional to the `log` (base 2) of the integer. Neither of these loops will execute more than log(n) time. – 24n8 Mar 16 '20 at 17:15
  • 1
    @GauravAgarwal good answer I would only add that `O(1)` for the 'sum of first n positive integers' algorithm relies on `O(1)` multiplication of arbitrarily large integers (which is a typical assumption) – ciamej Mar 16 '20 at 17:30
  • Your answer still reports that the runtime is proportional to the size of the inputs, but the runtimes are O(log n), not O(n). – templatetypedef Mar 16 '20 at 17:31
  • @templatetypedef as n grows so does O(log n). – Gaurav Agarwal Mar 16 '20 at 17:42
  • That's true, but log n is not directly proportional to n. – templatetypedef Mar 16 '20 at 17:49
  • @ciamej but multiplication is not really O(1), is it? – Quang Hoang Mar 16 '20 at 18:08
  • 1
    @QuangHoang in the most commonly assumed theoretical model of computation - the RAM model (https://en.wikipedia.org/wiki/Random-access_machine) it is assumed that registers are unbounded, and basic arithmetic operations are `O(1)` – ciamej Mar 16 '20 at 21:14
  • @ciamej it's really a fascinating topic. However, it confuses me that people are still in search for a [fast multiplication algorithm](https://en.wikipedia.org/wiki/Multiplication_algorithm). Is it possible to explain in a comment or should it be another question? – Quang Hoang Mar 16 '20 at 21:19
  • @QuangHoang I think that would be a great question! – ciamej Mar 16 '20 at 21:23
  • @QuangHoang obviously, the apparent conflict between `O(1)` multiplication and a fast multiplication algorithm is only abstract, on the level of formal models, not a practical one. Theoretical models, such as the RAM model, are not meant to represent reality as closely as possible, but to offer useful insights. I think this question deserves a much more thorough answer though. I'm not sure though, if computer science stack exchange wouldn't be a better fit for that question than SO. – ciamej Mar 16 '20 at 21:29
2

These loops each run in time O(log n). You can make an even tighter statement for the first one and say that it runs in time O(b), where b is the number of bits set in the number. It happens to be the case that b = O(log n) because the number n requires O(log n) bits to write out.

It's always a little bit dicey to talk about runtimes of algorithms that process numbers one bit at a time because you have two things in tension with one another. One is that, in a mathematical sense, the number of bits in a number grows logarithmically with the magnitude of the number. That is, the number of bits in the number n is O(log n). On the other hand, on actual machines there's a fixed limit to the number of bits in a number, which makes it seem like the runtime "ought" to be a constant, since you can't have unboundedly large values of n.

One mental model I find helpful here is to think about what it would really mean for n to grow unboundedly. If you have a 45-bit number, I'm assuming you're either

  1. working on a 64-bit system, or
  2. working on a 32-bit system and using multiple 32-bit integers to assemble your 45-bit number.

If we make assumption (1), then we're implicitly saying that as our numbers get bigger and bigger we're moving to larger and larger word size machines. (This can be formalized as the transdichotomous machine model). If we make assumption (2), then we're assuming that our numbers don't necessarily fit into a machine word, in which case the number of bits isn't a constant.

One last way to reason about this is to introduce another parameter w indicating the machine word size, then to do the analysis in terms of w. For example, we can say that the runtime of both algorithms is O(w). That eliminates the dependency on n, which may overestimate the work done.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • If we restrict the input to be 32-bit integers, could we make an even tighter statement and say that because `log(max(n)) = 32`, and `32` is a constant, then they run in O(1) time, or does this question not make sense in terms of asymptotic complexity analysis? – 24n8 Mar 16 '20 at 17:40
  • What's subtle here is that big-O notation talks about long-term growth rates for larger and larger values of n. If you believe that your values of n are constrained and can't exceed some value, then big-O notation is probably not the best mechanism for measuring runtime. – templatetypedef Mar 16 '20 at 17:50