318 views
2 votes
2 votes

solve   : Given T(1) =1 

$T(n) = 8T(\frac{n}{2}) + n^2$  

$T(\frac{n}{2}) = 8T(\frac{n}{2^2}) + (\frac{n}{2})^2$

$T(\frac{n}{2^2}) = 8T(\frac{n}{2^3}) + (\frac{n}{2^2})^2$

$T(\frac{n}{2}) = 8^2T(\frac{n}{2^3}) + 8(\frac{n}{2^2})^2 +(\frac{n}{2})^2$

Now, T(n) =  $8^3T(\frac{n}{2^3}) + 8^2(\frac{n}{2^2})^2 + 8(\frac{n}{2})^2 +(\frac{n}{2^0})^2$

now i always stuck after this  help plz , now when we check that which series is forming we have to take  $8^3T(\frac{n}{2^3})$  

seperate from $8^2(\frac{n}{2^2})^2 + 8(\frac{n}{2})^2 +(\frac{n}{2^0})^2$  and then  check  whic series is formed by $8^2(\frac{n}{2^2})^2 + 8(\frac{n}{2})^2 +(\frac{n}{2^0})^2$ 

or we have to take  whole $8^3T(\frac{n}{2^3}) + 8^2(\frac{n}{2^2})^2 + 8(\frac{n}{2})^2 +(\frac{n}{2^0})^2$

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
sumit goyal 1 asked Jan 8, 2018
211 views
$T(n) = 8T(\frac{n}{2}) + n^2$ T(1) = 1
1 votes
1 votes
0 answers
2
sumit goyal 1 asked Jan 8, 2018
153 views
$n^2 + 2n^2 + 4n^2 + - + 8^kT(\frac{n}{2^k})$T(1) = 1
2 votes
2 votes
0 answers
3
sumit goyal 1 asked Jan 15, 2018
1,189 views
A(n) = 7A(n-1) - 10A(n-2) + n , along with approach thankyou ,
2 votes
2 votes
0 answers
4
sumit goyal 1 asked Jan 15, 2018
499 views
solve : $a_{n} - 2a_{n-1 } = 3\times 2^n$ provide your approach thanks :)