Recurrence Relations with Geometric Series

297 Views Asked by At

if we have a situation where something is like this

$2^k + c(2^{k-1} + 2^{k-2} + 2^{k-3} + ... + 1)$

since in this case $r > 1$ then in Computer Science we look at $\sum_{i=1}^{n} r^{i} = \theta(r^{n})$

So in this case would we look at the $2^{k}$ or $2^{k-1}$?

1

There are 1 best solutions below

3
On

If you are asking to judge the order of the expression, then $$ 2^k + c\sum_{n=0}^{k-1}2^n = \Theta \left(2^k \right), $$ since the order of the summation does not affect the order of the expression.