algorithm - 嵌套 for 循环的 T(n) 时间复杂度

Question

void foo (int n, int val)
{
   int b,c;                                //+1
   for (int j = 4; j < n; j++)             //n  
   {
      for (int i = 0; i < j; i++)          //n 
      {
           b = b * val;                    // +1
           for (int k = 0; k < n; ++k)     // n 
                c = b + c;
      }
   }
}

我有上面的代码，当我尝试解决它时，我得到了 T(n) 的各种答案。从我的各种答案(n³-7n²+2)/2 和 ((n³ -5n² +6n)/2)+ 2n - 6，我得出的结论是 O(n) 是 O(n³)。我只需要找到正确的 T(n)。

Answer 1

现在是凌晨 4 点，所以我可能在胡说八道，但我的想法是:

第一个for是n-3次迭代

第二个 for 是 4+5+6+7+...+n-1 次迭代 => 1/2(n² - n - 12)

第三个for是n次迭代

(n-3)*(1/2(n² - n - 12))*n => O(n^4)