java - java代码的时间复杂度

Question

我正在 coursera 上学习算法类(class)，但我被困在这个特定问题上。我应该找出这段代码的时间复杂度。

int sum = 0

 for (int i = 1; i <= N*N; i = i*2)

  {
     for (int j = 0; j < i; j++)
           sum++; 
  }

我在eclipse里面查过，对于任意一个N值，sum语句执行的次数都小于N

final value of sum:
for N=8 sum=3 
for N=16 sum=7 
for N=100000 sum=511

所以时间复杂度应该小于N 但是给出的答案是N的2次方，这怎么可能？

到目前为止我做了什么:

第一个循环将运行 log(N^2) 次，因此第二个循环将执行 1,2,3.. 2 logN

Answer 1

第一个内部循环将是 1 + 2 + 4 + 8 .. 2^M，其中 2^M 是 <= N * N。

2 到 N * N 的幂之和大约为 2 * N * N 或 O(N ^ 2)

注意:当 N=100000 时，N*N 会溢出，因此其结果具有误导性。如果您认为溢出是问题的一部分，那么总和对于大数来说是相当随机的，因此您可以争论它的 O(1)，即如果 N=2^15，N^2 = 2^30 并且总和将为整数.MAX_VALUE。没有更高的 N 值会得到更高的总和。