最坏情况时间复杂度分析伪代码

有人可以帮我分析这个伪代码的时间复杂度吗？ 我正在寻找最坏情况的复杂度，但我无法弄清楚它是 O(n^4)、O(n^5) 还是完全其他的东西。如果您能详细说明您是如何解决这个问题的，我们将不胜感激。

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

第一个循环：O(n)

第二个循环：i处于平均水平n/2，你可以有一个精确的公式，但它是O(n²)

第三次循环发生i在第二个循环内的时间，所以平均n/2次。这是O(n²)以及，估计它。

So it's O(n*n²*(1 + 1/n*n²))， 我会说O(n^4). The 1/n来自第三个循环大致发生的事实1/n次在第二次之内。

这都是大概的估计，没有严格的证据，但应该是正确的。您可以通过自己运行代码来确认。