I have been having a debate with a couple of folks regarding the time complexity of this nested for loop algorithm:

for (i=1;i<=n;i*=2){
  for (j=1;j<=i;j  ) {
    // some O(1) operation
  }
}

Now I believe that the complexity of the algo is O(NlogN), reason being that the complexity of outer loop is O(logN) and that of inner loop is O(N).

However, a couple of folks have calculated the complexity of this algo to be O(N) using some method involving AP/GP.

What's the complexity of this algo? If it actually is O(N), what's the intuition behind it?

CodePudding user response：

The outer loop has a loop variable