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.



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.




Leave a Reply

Your email address will not be published. Required fields are marked *