runtime - 几何级数之和的 θ 表示法

Question

我有一个关于几何级数的问题。为什么是

1 + c + c² + ... + cⁿ = Θ(cⁿ)

当 c > 1 时？我明白为什么如果 c = 1 则为 θ(n)，如果 c < 1 则为 θ(1)，但我就是不明白为什么如果 c 则为 θ(cⁿ) >1.

谢谢!

Answer 1

几何级数前n项的和

c⁰ + c¹ + ... + c^n-1

由数量给出

(cⁿ - 1) / (c - 1)

请注意，如果 c > 1，则该数量从上方以 cⁿ - 1 为界，从下方以 c^n-1 - 1/c 为界。因此，它是 O(cⁿ) 和 Ω(cⁿ)，因此它是 θ(cⁿ)。

希望这有帮助!