Найти жесткую границу f (n) = 3logN + 1 + (1/2) + (1/2) ^ 2 + ... + (1/2) ^ n

Question

Это для анализа алгоритмов, и я не могу понять, с чего начать, как мне подойти к этому, чтобы найти решение?

Answer 1

Поскольку сумма рядов S = 1 + 1/2 + 1/2^2 + ... + 1/2^n постоянна, f(n) = Theta(n).

Мы знаем, что S = (1 - 1/2^(n+1)) / (1 - 1/2) и n уходит в бесконечность S уходит в 2.Следовательно, предел f(n) с ростом n равен 3 log(n) + 2.

Answer 2

Сумма 1 + 1/2 + 1/4 + 1/8 +… + 1/2 ⁿ постоянна.Действительно, это геометрическая прогрессия [wiki] .Сумма:

 n
---
\     1
/    ----
---   2<sup>n</sup>
i=0

совпадает с 2-1 / 2 ⁿ , если n уходит в бесконечность, сумма в конечном итоге перейдет к 2 (не бесконечность).

Таким образом, это означает, что 3 × log (n) + 1 + 1/2 + 1/4 +… + 1/2 ⁿ эквивалентно 3 × log (n) + 2-1 / 2 ⁿ .Для асимптотики n это, таким образом, эквивалентно Θ (3 × log n) и, таким образом, Θ ( log n) .