in Algorithms
326 views
2 votes
2 votes
Consider the following recurrence relation.

$$T(n) = \begin{cases}1 & \quad  if \: n = 1 \\ T(n-1) + 2^n \quad & otherwise \end{cases}$$

What will be the value of $T(10)$?
in Algorithms
by
326 views

2 Answers

4 votes
4 votes
Best answer
$T(n) = T(n-1) + 2^{n}$

$T(n) = T(n-2) + 2^{n-1} + 2^{n}$

$T(n) = T(n-3) + 2^{n-2} + 2^{n-1} + 2^{n}$

$T(n) = T(n-k) + 2^{n-k+1}+.... + 2^{n-1} + 2^{n}$

$\text{Now at }k = n - 1$,

$T(n) = T(1) + 2^{2}+.... + 2^{n-1} + 2^{n}$

$T(n) = 1 + 2^{2}+.... + 2^{n-1} + 2^{n}$

$T(n) = \left ( 2^{0} + 2^{1} + 2^{2}+.... + 2^{n-1} + 2^{n} \right ) - 2^{1}$

$T(n) = 2^{n+1} - 1 - 2$

$T(n) = 2^{n+1} - 3$

$\therefore T(10) = 2^{10+1} - 3 = 2048 - 3 = 2045 $
selected by
4 votes
4 votes
$T(1) = 1$
$T(2) = T(1) + 2^2 = 5$
$T(3) = T(2) + 2^3 = 13$
$T(4) = T(3) + 2^4 = 29$
$T(5) = T(4) + 2^5 = 61$
$T(6) = T(5) + 2^6 = 125$
$T(7) = T(6) + 2^7 = 253$
$T(8) = T(7) + 2^8 = 509$
$T(9) = T(8) + 2^9 = 1021$
$T(10) = T(1) + 2^{10} = 2045$

$T(n) = \begin{cases}1 & \quad if \: n = 0 \\ T(n-1) + 2^n \quad & otherwise \end{cases}$

then answer would be 2047.

3 Comments

yes, answer changed and your marks are updated :)
1
1
ans is 2045 or 2047??
0
0
2045.
0
0
Answer:

Related questions