548 views

2 Answers

Best answer
4 votes
4 votes
$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.
Answer:

Related questions

2 votes
2 votes
2 answers
1
Bikram asked Oct 4, 2016
347 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
2 votes
2 votes
1 answer
4
Bikram asked Oct 4, 2016
539 views
While inserting keys 12,44,13,88,23,94,11,39,20,16 and 5 in a 11 item hash table using the hash function $h(i) = (2i+5) \mod 11$, total number of collisions that occur ...