Временная сложность циклов внутри рекурсивной функции

Question

Скажем, есть рекурсивная функция, которая выполняется n раз, и вложенный цикл for, который выполняется n ^ 2 раза, какова будет его временная сложность 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 ^ 2) (n + 1) / 2, что равно O (n ^ 3).