In problem “count set bits” in first method bhaiya is saying time complexity of 1st method is o(log n+1) bits and in 2nd method o(no. of set bits) so i want to understand what bits bhaiya is talking about and which time complexity is bettero(n) or o(log n)
Problem related to rime complexity
Hey @vikash3303 ,
In the first method , what we are doing is checking the last bit of the number and if the last bit of the number is 1 then adding it to the answer and otherwise not adding it to the answer .
Any number n can be represented by logn + 1 bits .
In this method we are traversing every bit . Therefore we are traversing logn +1 bits so the time complexity of the first method is O(LogN) .
In 2nd method , The algorithm only checks the set bit of the number . So the number of iteration will be the no of set bits in the number .
for ex : 9 - 1001 has 2 set bits so the number of iteration for this number is 2 .
15 - 1111 has 4 set bits so the number of iterations for this number is 4.
Time complexity of this solution is O(No of set bits of the number) Note that the no of set bits is not n itself .
Comparision between the two method is : 1st method is slower than 2nd method because 1st method is checking all the bits of the number where as the 2nd method is running for the no of set bits present in the number .
Hope you understand this now . Happy coding ! 