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;
    while ( n-- ) {

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

            k = ( 1 << i );
            m = k | n;
            if ( m == n ) count++;
    cout << count;
    return 0;
4 Years
Discussion Span
Last Post by vijayan121

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).

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.