T (n) = T (n-1) + O (log n) $ является T (n) = O (n^2) или T (n) = O (n log n)

Question

У меня это отношение повторения : T (n) = T (n-1) + O (log n)

Какое решение? T (n) = O (n^2) или T (n) = O (n log n)

Что я сделал: Предполагаю, что T (n) < = O (n^2) ...

И это приводит меня к O (n^2), я прав?
Или у меня есть ошибка? (Я слышал от кого-то, что он получил O (n log n), и я кейс, если я прав или он ...)

Спасибо!

Answer 1

, если Т (п) < = Т (п-1) + с п лог для некоторого с

=> Т (п) < = Т (п-2) + с лог (н- 1) + с лог-н

=> Т (п) < = Т (п-3) + с лог (п-2) + с лог (п-1) + с лог-н

следующим образом: T (n) < = T (0) + sum_ {i = 1 .. n} c log i = O (n log n)

, но O (n^2) также является правильным, но менее конкретным, так как T (N) = O (N^2) означает, что

есть некоторые а, т таким образом, что Т (п) = а < п^2 для всех п> = т