Как доказать сложность T (n) = T (n-1) + log n = Θ (nlog n)

Question

Как я могу доказать это T (n) = T (n-1) + log n = Θ (nlog (n))

Мое мышление:

Мы можем получить T (n) = ∑log (n). Чтобы доказать результат, мы должны доказать, что ∑log (n)> = Nlog (N) и ∑log (n) <= Nlog (N). Второе легко, я хочу знать, как доказать ∑log (n)> = Nlog (N)?

Answer 1

Предположим N > 10. (Вам нужно только доказать оценку для «достаточно большого» * ​​1002 *.)

Предположим, у нас есть sum_n log(n), но мы игнорируем условия, где n < N/10. У нас осталось 9/10 * N терминов, и каждый термин не менее log(N/10). Тогда:

sum_n log(n) >= (9/10 * N) * log(N/10) = (9/10 * N) * (log(N) - log(10)) = (constant) * N * log(N) - (constant) * N

что явно Omega(N log N).