project_ananthu - 1 month ago 5x
C Question

# How to calculate the Time complexity of my C function

I wrote a function to calculate the number of ones in the binary of a decimal number. If the input is 3 then its binary will be 0011 and it should print the output as two. Because there are two 1 in the binary number.How can i calculates time complexity of this function?

``````    #include<stdio.h>
void main()
{
void numberof_1(int n)
{
int i,count=0;
if ((n & 1)== 1)
count=count+1;
printf("%d",count);
for(i=0;i<32;i++)
{
n= n >> 1;
if ((n & 1)==1)
{
count=count+1;
}
}
printf("\nthe number of ones =%d\n",count);

}
numberof_1(10);
}
``````

When speaking from purely algorithmic point of view, the time complexity of `numberof_1()` is `O(log(n))` (where `n` is the input number).
The number is represented in binary base, and thus have `log_2(n)` bits representing it. Your algorithm is iterating all these bits.
However, note that to really achieve that `O(logn)` time complexity, you should add a conditional `break` when `n==0` (to avoid redundant iterations on a number which is already 0).
From technical point of view, integers are represented by constant number of bits, and if you refer to this size as constant indeed - the algorithm run time is `O(1)`, as the number of iterations is limited and there is a hard bound for the number of iterations needed.