in this code i am counting the number of bits present in the numbers from 1, 2, 3....n i.e the total number of the set bits present in all the numbers till n, what should be the complexlity of this code of mine please any one tell and also how it should be calculate.

``````#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

int main()
{
int n, count, m, k;
count = 0;
cin >> n;
n++;
while ( n-- ) {

for ( int i = 0; i <= n ; i++ ) {
if ( (1 << i) > n ) {
break;
}

k = ( 1 << i );
m = k | n;
if ( m == n ) count++;
}
}
cout << count;
return 0;
}
``````

`O(mn)` where `m` is the number of integers you process and `n` is the number of bits in an integer.

How did I figure that out? The outer loop is obviously `O(n)`. The inner loop is also obviously `O(n)` and adds to the outer loop, but the value of `n`

## All 2 Replies

`O(mn)` where `m` is the number of integers you process and `n` is the number of bits in an integer.

How did I figure that out? The outer loop is obviously `O(n)`. The inner loop is also obviously `O(n)` and adds to the outer loop, but the value of `n` differs from the outer loop, so the complexity isn't `O(n^2)`. `O(m) * O(n)` (changing one of the `n`s to `m` to differentiate them) is simplified to `O(mn)`.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.