457 views
3 votes
3 votes

2 Answers

1 votes
1 votes

I just take some eg here. Here we can also use substitution method which will give GP series of 2n  cancellation of series of 2n  remaining term is 1, that's another way to approach this problem

0 votes
0 votes

t(n)=2t(n-1)-1 ->4t(n-2)-2-1->8t(n-3)-4-2-1->...

t(n)=2nt(n-n)-2n-1-2n-2......-4-2-1  .->..2n-(2n-1/2-1)GPsum  => 2n-2n+1=1

Related questions

3 votes
3 votes
2 answers
1
Diksha Aswal asked Jul 3, 2017
1,855 views
T(n) = T(n/3)+T(2n/3)+n What is the solution of Above Given recurrence relation?Give full method to solve this
2 votes
2 votes
4 answers
3
Anjana Babu asked Dec 31, 2016
1,133 views
On solving the RecuranceT(n) = 3T(n/4) + cn2I was stuck at summation$\sum_{i=0}^{log_4 n} (\frac{3}{16})^{i} cn^{2}$Can someone could help ?
0 votes
0 votes
1 answer
4
PEKKA asked Dec 6, 2016
7,044 views
Solve the following Recurrence Equation using back substitution methodT(n)= T(n-1)+log n​