runtime complexity linear when suspected n log n

Viewed 93

Having trouble understanding why time complexity of this snippet is O(n)

int main() {
  int n = 10; //n can be anything
  int sum = 0;
  float pie = 3.14;
  int var = 1;

  while (var < n){
    cout << pie << endl;
    for (int j=0; j<var; j++)
      sum+=1;
    var*=2;  
  }
  cout<<sum;
}

The bisection of var means log(n) and then there is a nested inner loop which apparently has 2n making the overall complexity O(n). But I dont get why 2n.

1 Answers

It might be helpful to consider the case when n is a power of 2: n = 2^m. Then the number of iterations in the code (which is also, conveniently, the number it calculates) is

1 + 2 + ... + 2^(m-1) =
2^m-1 <
n =
O(n)
Related