complexity

[amit43]

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;
}

[deceptikon]

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 ns to m to differentiate them) is simplified to O(mn).

[vijayan121]

For an O(log n) algortithm, see:
http://stackoverflow.com/questions/9812742/finding-the-total-number-of-set-bits-from-1-to-n