1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

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