170
правок
Изменения
Нет описания правки
Рассмотрим эту сумму:
<tex>\sum\limits_{k = log_{1/p} n}^{\infty} k \cdot p^k = p^{log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + log_{1/p} n) \cdot p^k = p^{log_{1/p} n} \cdot (\sum\limits_{k = 0}^{\infty} (k p^k) + log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{log_{1/p} n} \cdot (O(1) + log_{1/p} n \cdot O(1)) = O(log(n) \cdot 1/n)</tex>
Суммируя всё вышесказанное, получаем, что <tex>O(log(n))</tex>.
