algorithm - Get time complexity of the recursion: T(n)=4T(n-1) - 3T(n-2) -


i have recurrence relation given by:

t(n)=4t(n-1) - 3t(n-2) 

how solve this? detailed explanation:

what tried substituted t(n-1) on right hand side using relation , got this:

 =16t(n-2)-12t(n-3)-3t(n-2) 

but don't know , how end this.

not can time complexity of recursion, can solve exactly. exhaustive theory behind linear recurrence relations , 1 called here specific case of homogeneous linear recurrence.

to solve need write characteristic polynomial: t^2 -4t +3 , find it's roots t=1 , t=3. means solution of form:

t(n) = c1 + 3^n * c2.

you can c1 , c2 if have boundary conditions, case enough claim o(3^n) time complexity.


Comments

Popular posts from this blog

php - Submit Form Data without Reloading page -

linux - Rails running on virtual machine in Windows -