3 ms·
"While I agree that this is the right answer, questions regarding "Big-O" are trying to find out whether or not you can evaluate the complexity of an algorithm.
by jerf 9y ago
"While I agree that this is the right answer, questions regarding "Big-O" are trying to find out whether or not you can evaluate the complexity of an algorithm."
Most algorithms for counting bits will be O(1) for a given int, so O(number of ints) for a list of ints. Algorithms that aren't O(1) for a given int [1] will still be essentially O(1) since the upper bound would be so tight. So I don't think that was a Big-O question.
[1]: "count = 0; while i != 0 { count += i % 2; i >> 2 }". Technically this is O(leftmost set bit), but on a fixed-bit int could be considered O(1) with a suitable constant. Note that algorithm isn't entirely pointless; it works on bigints too, so in something like Python where ints and bigints are not distinguished by type you could use it as a fallback for "generic int" (which may include user-defined classes). (Though of course there are ways to speed it up.)