Решение рецидивов с использованием мастер-метода

Question

Я пытаюсь решить рекуррентное соотношение, чтобы выяснить сложность алгоритма, который я написал.Это уравнение ..

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

И я нашел ответ на O (n2), но яне уверен, правильно ли я это сделал.Может кто-нибудь подтвердить, пожалуйста?

Обновление: что если уравнение T (n) = T (n-1) + Θ (nlogn)?Это все еще будет O (n2)?

Answer 1

Да, вы угадаете это правильно.

Однако форма повторения не соответствует методу Master.Так как вы угадали границу правильно, метод замещения здесь больше подходит.

Теперь ваша работа - найти две константы c и n0, чтобы доказать, что:

T(n) <= c*(n^2) forall n >= n0

Answer 2

Это O (N) + O (N-1) + ... + O (1) = O (N * (N + 1) / 2). Так что да, общая сложность квадратична.