1
$\begingroup$

I'm more concerned with just finding big oh since that can be used to find big omega. I am also told I cannot use limits to find the answer.

I'm given: $3+9+27+\dots+3^n$. My first assumption is that $3^n = \Theta(3^n)$. The method we're supposed to use goes something like this:

$3+9+27+\dots+3^n<3^n+3^n+\dots+3^n$

Or I think that's what we're supposed to do here. I'm not sure how to simplify a sequence of repeating $3^n$ in order to find a constant C.

Any help is appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ "finding big oh since that can be used to find big omega" -- no, it can't. $\endgroup$ – Raphael Jul 21 '14 at 0:00
7
$\begingroup$

First, your assumption, I'm more concerned with just finding big oh, since that can be used to find big omega is a bit dangerous. You could indeed easily find a $O()$ upper bound for your sum, $S(n)=3^1+3^2+3^3+\cdots+3^n$ by observing that each term is less than $3^n$ so you could have $$ 3^1+3^2+\cdots+3^n\le \underbrace{3^n+3^n+\cdots+3^n}_{n}=n3^n=O(n3^n) $$ but that's a huge overestimate (try it for, say, $n=5$) and so will almost certainly not serve as a suitable big-Omega bound*. Instead, you could simply use the formula for a geometric series and get an exact value, but suppose you didn't know that formula (or were prohibited from simply invoking it).

On the way to finding a good estimate, you could always try this helpful idiom: We've written $S(n)=3^1+3^2+3^3+\cdots+3^n$ and so we also have $S(n+1)=3^1+3^2+3^3+\cdots+3^{n+1}$ so $$\begin{align} S(n+1)-3S(n)&=(3^1+3^2+\cdots+3^{n+1})-3(3^1+3^2+\cdots+3^n)\\ &=(3^1+3^2+\cdots+3^{n+1})-(3^2+3^3+\cdots++3^{n+1})\\ &= 3 \end{align}$$ But we also know that $S(n+1)=S(n)+3^{n+1}$ so we have $$ 3=S(n+1)-3S(n)=S(n)+3^{n+1}-3S(n)=-2S(n)+3^{n+1} $$ and so with a little algebra we find $$ S(n) = \frac{3^{n+1}-3}{2}=\frac{3}{2}(3^n-1) $$ Since we have an exact value for the sum, we can easily see that $S(n)=\Theta(3^n)$. However, if you need to establish explicit constants to show $S(n)\ge c\,3^n$ (for big-omega) and $S(n)\le d\,3^n$ (for big-o) it's not too difficult. (Hint, can you see that you can use any $d\ge 3/2$?)


$^*$As an aside, you might have been misled in your choice of replacements at the very start by the proof that $1^k+2^k+3^k+\cdots+n^k\le n^k+n^k+\cdots+n^k=n^{k+1}$ which does indeed lead to a big-Theta estimate, though for a different sum.

$\endgroup$
2
  • 1
    $\begingroup$ Essentially, the technique is converting the sum into a recurrence without full history and then solve it. $\endgroup$ – Raphael Jul 21 '14 at 0:04
  • $\begingroup$ This was a better explanation than my text book provided for any example. Thank you. $\endgroup$ – douglas Jul 21 '14 at 16:12
3
$\begingroup$

Hint: use the formula for the sum of a geometric series.

Note that, when you write $3^n + \dots + 3^n$, you have $n$ terms so that sum evaluates to $n3^n\notin\Theta(3^n)$.

$\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.