algorithm - 计算大 O 符号 : O(n^4) for 2 nested loops and O(log n) with no recursion

Question

自从我完成一些运行时复杂度近似练习以来已经有一段时间了，我一直在努力思考以下在网上找到的示例(评论是我自己的):

示例 1:

for ( int i = 1 ; i <= n ; i++) { //n
  for ( int j = 1; j <= i*i ; j++) { // 1+2^2+3^2+...+n^2
    if ( j % i == 0) {
      for ( int k = 0 ; k < j ; k++ ){ // 1+2^2+3^2+...+n^2
        sum++;
       }
      }
     }
    }

解决方案表上说它是 O(n^4)，但我看不到。我确定我错过了一些东西，因为在我的评论中我计算过在最坏的情况下它是 O(n^5)。

示例 2:

i = 1 ;
L2 = -1;
while ( i <= n ) {
  i = i*2 ; // 2 + 2^2 + 2^3+ ...+ 2^n
  L2++;
}

提到的解决方案是 O(log n)。我认为在最坏的情况下，我会得到类似于 2^n <= n 的结果，因此 n <= log n。在这里应用上界函数的典型定义(即 f(n) <= O(g(x)) )会更直观

我基本上想知道我错过了什么，以及我应该经历哪些步骤/指南才能为这两种情况(尤其是第一个示例)找到正确的大 O 复杂度。对于任何不清楚的细节，我深表歉意，我很乐意添加更多说明。提前致谢，感谢任何见解!

Answer 1

示例 1 是 O(n^5) 因为大 O 是上限。它也是 Theta(n^4) 因为 if 语句使得最里面的循环只在每 i 次迭代中运行，所以运行时间是 Theta(n sum_{i =1}^n (i*i * 1/i * i*i)) = Theta(n^4).

示例 2 是 O(log n)。在第 j 次迭代中，i 为 2^j，2^j > n 的阈值为j > lg n.