c - 递归函数内循环的时间复杂度

Question

假设有一个运行 n 次的递归函数和一个运行 n^2 次的嵌套 for 循环，那么它的时间复杂度是 O(n) 或 O(n^3)

例如:

fun(int n) {
if(n==1) return;

for(i=0;i<n;i++) 
  for(j=0;j<n;j++) 
    printf("A");

}

Answer 1

上述函数的时间复杂度为O(n^3)。

看起来对于每个n，循环s将运行n(n+1)/2次，并且这将发生n次。因此总迭代次数为 (n^2)(n+1)/2，即 O(n^3)。