Problem 9E

Give a big-O estimate for the number of comparisons used by the algorithm that determines the number of 1s in a bit string by examining each bit of the string to determine whether it is a 1 bit (see Exercise 25 of Section 3.1).

Solution

In this question we have to give big-O estimate for the number of comparisons used by the algorithm that determines the number of 1s in a bit string by examining each bit of the string to determine whether it is a 1 bit.

Step 1

Time Complexity : Total time required by the program to run to completion.

It is commonly expressed in the terms of big-o notation.

It is estimated by counting number of elementary operations run by algorithm.

It is represented by T(n).