3
$\begingroup$

So I'm doing exercises from Dasgupta's Algorithms. The exercise i'm having trouble with is:

Show that, if $c$ is a positive real number, then $g(n) = 1 + c + c^2 +...+c^n$ is:

  1. $\Theta(1)$ if $c<1$

  2. $\Theta(n)$ if $c=1$

  3. $\Theta(c^n)$ if $c>1$

(I dont know if this is a hint but it is included in the text: "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 indreasing or the number of terms if the series in unchanging")

The only one that makes sense for me is 2) where $1+1^2+..+1^n$ is the same as $n+1$, and removing the 1 gives $O(n)$. I dont know if my reasoning makes sense, but thats all i've got. I have no idea where to start or how to think on the other two. Any suggestions?

$\endgroup$
  • 2
    $\begingroup$ 1) Check a formulary of your choosing for closed forms of this sum. 2) Apply the usual machinery. -- that doesn't sound all too arcane to me, so I have to wonder where you are coming from, and what specifically your problem is. $\endgroup$ – Raphael Aug 30 '16 at 18:29
  • 4
    $\begingroup$ Do you know the formula for a geometric series? That should completely answer your question. $\endgroup$ – Rick Decker Aug 30 '16 at 20:13
1
$\begingroup$

Hints:

  • In the first case, use the inequalities $$ 1 \leq \sum_{i=0}^n c^i = \frac{1-c^{n+1}}{1-c} \leq \frac{1}{1-c}. $$

  • In the second case, use the inequalities $$ c^n \leq \sum_{i=0}^n c^i = \frac{c^{n+1}-1}{c-1} \leq \frac{c}{c-1} c^n. $$

$\endgroup$
1
$\begingroup$

For an intuition of the first case, start with a decreasing geometric sum with an infinite number of terms. Calculate $c \cdot g(\infty) = c + c^2 + \ldots$, and $g(\infty) - c \cdot g(\infty) = 1$, so $g(\infty) = 1/(1-c)$. Clearly $g(n) \leq g(\infty)$ for any positive $c$, and so the entire series (infinite or finite) asymptotically matches the first term.

For an intuition of the 3rd case, take the sum to be $1 + d + d^2 + \ldots + d^n$, where $d>1$, and then let $c = 1/d$, so $c<1$. Now, $1 + d + d^2 + \ldots + d^n = d^n(c^n + c^{n-1} + c^{n-2} + \ldots + 1)$. That parenthesized sum on the right is your finite decreasing geometric series from the first case (in reverse order), which grows asymptotically like $\Theta(1)$, so your entire term grows like $d^n$, the last term of the finite sum.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.