Question

Identify the best 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.

Answer 1

Answer:

0(n)

Step-by-step explanation:

Result previous exercise:  

procedure count(a1a2...an : string with n > 1)

i:=0

for k:=1 to n

if ak =1 then i:=i + I

return i  

Note: If you use a different algorithm, then you could possible get different results.  

SOLUTION  

There is only one part of the code that contains an operation (comparison), namely if a_k =1  

This comparison is executed in every iteration of the for-loop  

k can take on the values from 1 to n (for k:=I to n), thus k can take on n values.  

Thus in total there are then n comparisons, while n is 0(n).