找到 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。因此，随着 n 的增长，f(n) 的极限是 3 log(n) + 2.

Answer 2

1 + 1/2 + 1/4 + 1/8 + … + 1/2ⁿ的总和是常量.确实，这是一个gemetric progression [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).

Find the tight bound of f(n)=3logN + 1 + (1/2) + (1/2)^2 + ... + (1/2)^n