Register

Recurrence Relation

• retagged by
907 views
1 votes
1 votes
T(n) = T(n-1) + T(n-2) + c  i want solve it using substitution method..

T(n) <= 2 T(n-1) + c     is this a correct way ??

plz explain ...

if its wrong then what is correct way
• retagged by
User Avatar

2 Answers

1 votes
1 votes
yes u can solve like that.but

use intuition when such kind of qus comes

dnt go for substitution bcz it takes lot of time..
User Avatar
0 votes
0 votes
put m=n-1

T(n-1)=T(m)

=T(m-1)+(m-2)+c

Therefore

T(n)= T(n-1)+

T(n-2)
+c
= T(n-2)+T(n-3)    +

T(n-3) + T(n-4)
+c
=T(n-3)+T(n-3-1) +T(n-3)+

T(n-3)+T(n-3-1)
+c
=3*T(n-3) + 2*T(n-3-1)+c
when base conditions for T(2) and T(1) are  given

we get

T(n)= (n-2)*T(n-(n-2)) + (n-1)* T(n-(n-1))

=(n-2)*T2   +  (n-1)*T1     +c
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
jenilS7 asked Mar 18
139 views
Recurrence relation
What is the returned value by the given function below. Algo fun(n) { If(x<=2) return 1; Else { Return fun(n1/2) + n; } } Note : Assume that all the syntax and data type constraints are valid and just check algorithm.
What is the returned value by the given function below.Algo fun(n){ If(x<=2) return 1; Else { Return fun(n1/2) + n; }}Note : Assume that all...
User Avatar
0 votes
0 votes
1 answer
2
vivek1211 asked Oct 2, 2023
268 views
solve this recurrence relation
T(n) = T(n^1/2) + n doing this in substitution method gives the ans as O(n) but using tree recursion gives the ans as O(nlogn) which of these are correct and which has to be considered for worst case
T(n) = T(n^1/2) + ndoing this in substitution method gives the ans as O(n)but using tree recursion gives the ans as O(nlogn)which of these are correct and which has to be...
User Avatar
0 votes
0 votes
0 answers
3
rexritz asked Aug 13, 2023
308 views
How to solve the following recurrence relation? I get confused when decimals are used in the expression.
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
User Avatar
1 votes
1 votes
0 answers
4
srestha asked May 19, 2019
639 views
Recurrence Relation-Self Doubt(Discrete Math+Algo)
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Complexity??
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
User Avatar
Link Copied!