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
Post a Comment