Временная сложность T (n) = T (n - 1) + (n - 1) ^ 2

Question

Мне интересно, какова временная сложность этого рекуррентного отношения.

Answer 1

Извините, если я пишу изображениями, но мне нужно было включить математику:

Answer 2

T (n) = T (n-1) + f (n)

Средние

T (n) = T (0) + Sum_from_i = 1_to_n_of (f (i) )

В вашем случае это:

T (n) = T (0) + 0 ² + 1 ² + 2 ² ... (n-1) ²

Если вы не знаете сразу из дискретного исчисления, что сумма составляет O (n ³ ), вы можете заметить, что существует n членов, наибольшее из которых (n-1) ² , и более (n / 3) членов, которые> = (n / 2) ² .