0

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}$?

MD_90
  • 103

1 Answers1

0

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.

gt6989b
  • 54,422
  • so if we have cases like that just look at $2^{k}$ where base can be any – MD_90 Apr 22 '15 at 00:24
  • @MD_90 not so simple. Notice that $5^{k-1} >> 2^k$ even though the exponent is smaller since $2^k = 2 \cdot 2^{k-1}$... – gt6989b Apr 22 '15 at 00:26
  • interesting, since its a geometric series and r > 1 then the largest exponent is $2^{k}$ even though the series is $2^{k-1}$ + ... + 1. Say k= $\log_3 n$ and that same equation is as follows...

    $2^{log_3 n} + c\sum_{i=0}^{\log_3 n} 2^{i} = \theta(n)$

     – MD_90 Apr 22 '15 at 01:11