algorithm - Big-O 时间复杂度，嵌套 for 和 while 循环

Question

我正在尝试理解 Big-O 时间复杂度，不幸的是，我在挣扎，我似乎无法理解这个概念，我知道我的结果对于以下两个代码片段是正确的，但是我到达那里的方式似乎是错误的。有人可以帮助解释我误解的地方吗(请不要，但是不要使用 sigma。谢谢!

Code Fragment               Time Complexity
sum ← 0                     O(1)
  for i ← 1 to n do         O(n)
    for j ← 1 to n do       O(n)
      k←1                   O(1)
      while k < n do        
        k ← k * C           O(log n)  - affected by C (due to multiplication)
        sum ← sum + 1       O(1)
                            -----------
                            O(1 x n x n x 1 x [log n] x 1)
                            O(n2 log n)

Code Fragment             Time Complexity
sum ← 0                   O(1)
 for i ← 1 to n do        O(n)
  for j ← 1 to i do       O(n) 
    k←1                   O(1)
    while k < n do      
      k ← k + C           O(n) – not affected by C, k is arbitrarily large
      sum ← sum + 1       O(1)
                            -----------
                          O(1 x n x n x 1 x n x 1)
                          O(n^3)

Answer 1

虽然最终结果是正确的，但我在计算中发现了一些小错误。

在第一个算法中:

O(1 x n x n x 1 x [log n] x 1)

应该是

1 + n x n x (1 + (O(log n) x 2)) = O(n^2 * log n)

在第二种算法中:

O(1 x n x n x 1 x n x 1)

应该是

1 + n x O(n) x (1 + (O(n) x 2)) = O(n^3)