Question-63
Give a big-O estimate for the number of comparisons used by the algorithm that determines the number of 1 s in a bit string n by examining each bit of the string to determine whether it is a 1 bit.
Solution
The number of comparisons is O(n) , where is the number or bits in the string. Each bit must be examined to see if it is a 1 bit, therefore there must be least n comparisons to check bit.