Finding the geometric sum of this recurrence

Question

I'm having trouble with evaluating geometric sequences that look like this:

$Cn\sum_{i=0}^{\log_3n} (5/3)^i$

where $n$ is the number of operations, and $Cn$ just represents $n$ times some constant $C$. I'm trying to get the big $O$ of this, but I'm not quite sure.

Is it equal to $O(n^{log_35})$?

Also, if it was $(3/5)^i$ instead, would it just be $O(1)$?

Thanks!

Answer 1

We have \begin{align} T(n) &=Cn\sum_{i=0}^{\log_3n} (5/3)^i\\ &=Cn\frac{(5/3)^{1+\log_3(n)}-1}{5/3-1}\\ &=\frac 32Cn((5/3)^{1+\log_3(n)}-1)\\ &\sim\frac 52Cn\left(\frac 53\right)^{\log_3(n)}\\ &=\frac 52C5^{\log_3(n)}\\ &=\frac 52C5^{\log_5(n)/\log_5(3)}\\ &=\frac 52Cn^{1/\log_5(3)}\\ &=\frac 52Cn^{\log_5(5)/\log_5(3)}\\ &=\frac 52Cn^{\log_3(5)} \end{align} hence $T(n)\in O(n^{\log_3(5)})$, otherwise \begin{align} T(n) &=Cn\sum_{i=0}^{\log_3n} (3/5)^i\\ &\sim \frac 52Cn \end{align} hence $T(n)\in O(n)$.