第一个循环： O（N）

第二循环：我是平均 N / 2 ，你可以有一个确切的公式，但它的 O（N²）

三环路发生我倍的第二循环中，使平均的N / 2 次。而且它的 O（N²）为好，估计它。

因此​​，它是 O（N *N²*（1 + 1 / N *N²）），我会说为O（n ^ 4 ）。该 1 / N 来自该第三循环发生大约 1 / N 时间内的第二个。事实

这都是一个大概的估计，没有严格的证明，但它应该是正确的。你可以通过运行code自己确认。

Could someone help me out with the time complexity analysis on this pseudocode? I'm looking for the worst-case complexity here, and I can't figure out if it's O(n^4), O(n^5) or something else entirely. If you could go into detail into how you solved it exactly, it would be much appreciated.

sum = 0
for i = 1 to n do
   for j = 1 to i*i do
       if j mod i == 0 then
          for k = 1 to j do
              sum = sum + 1

First loop: O(n)

Second loop: i is in average n/2, you could have an exact formula but it's O(n²)

Third loop happens i times inside the second loop, so an average of n/2 times. And it's O(n²) as well, estimating it.

So it's O(n*n²*(1 + 1/n*n²)), I'd say O(n^4). The 1/n comes from the fact that the third loop happens roughly 1/n times inside the second one.

It's all a ballpark estimation, with no rigorous proof, but it should be right. You could confirm it by running code yourself.