Algorithims, Geometric Sequences Show that, if c is a positive real number, then

Question

Algorithims, Geometric Sequences

Show that, if c is a positive real number, then g(n)= 1 + c + c^2 + c^n is: (a) theta(1) if c 1. The moral: in big-theta terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

Explanation / Answer

Given the formula for the sum of a partial geometric series, for c != 1: n+1 n+1 1 - c c - 1 g(n) = ---------- = ---------- 1 - c c - 1 (a) c < 1 n+1 1 > 1 - c > 1 - c 1 ------- > g(n) > 1 1 - c (b) c = 1 g(n) = 1 + 1 + 1 + ... + 1 = n + 1 = O(n) (c) c > 1 n+1 n+1 n c > c - 1 > c c n 1 n ------- c > g(n) > ------- c 1 - c 1 - c

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---