GATE Overflow | Algorithms | Test 1 | Question: 10

Question

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

Answer 1

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

Answer 2

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

Comments

yes, answer changed and your marks are updated :)

---

ans is 2045 or 2047??

---

2045.