带有嵌套for循环的bar函数的时间复杂度是多少？

bar (a) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
      a = a * (i + j);

  return a;
}

该函数的时间复杂度为 O(n²)。

• 外层for循环的控制变量i从0遍历到n-1，总执行次数为n次。
• 内层for循环的执行次数和外层i的取值正相关：当i取值为k时，内层j从0遍历到k-1，对应执行k次。
• 两层循环的总执行次数为等差数列求和：$0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2}$，忽略低阶项和常数系数后，最终时间复杂度为O(n²)。

内容的提问来源于stack exchange，提问作者Tayyab