Question

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).

Short answer

The algorithm requires a total of O(n) comparisons.

Step-by-step solution

Writing the algorithm:

Procedure ones ( a: bit string $a=a_1,a_2,...,a_n$)

$\begin{array}{r}\text{count}:=0\\ \text{for}i:=1\text{to}n\\ \text{if}{a}_i=1\text{then}\\ \text{count}:=\text{count}+1\\ \text{return count}\end{array}$

Counting the total number of comparisons:

We notice that the loop runs for a total of n time steps

Also, there is one comparison for each run of the loop

Thus, there are a total of n comparisons (ignoring the ones used in checking the condition in for loop).

Therefore, the algorithm requires a total of O(n) comparisons.