Solving recurrence using characteristic equation

user_1583358 0
Viewed 152

I am recently learning the how to use the various methods to solve recurrences. So far I have acquainted myself with the Master's Theorem and Substitution method. One method I just can't seem to understand is the following question which needs to be solved by characteristic equation:

T(n)=2T(n/3)+1,T(1)=1

I watched certain tutorials and readings and I imagine I needed to derive some sort of degree and simultaneous equation out of this?

How do I do it in this case?

Sorry for being amateur at this.

recurrence algorithm
1 Answers

First we have to put the recurrence in a more standard form. Let U(k) = T(3k). Then

U(0) = 1
U(k) = 2 U(k−1) + 1

U is defined by a non-homogeneous linear recurrence equation. The next step is to get the nontrivial solutions to the homogeneous part:

V(k) = 2 V(k−1)

The characteristic polynomial is x − 2, with a single root x = 2, hence the solutions are c 2k for every c. (If there were more than one root, we'd consider every linear combination of the exponential function for each root.)

Now we have to get any solution at all satisfying U(k) = 2 U(k−1) + 1, never mind the base case. If the extra term is a polynomial, we can find a polynomial. In this case, we can try a constant function, solve x = 2 x + 1, get x = −1, and verify that U(k) = −1 in fact works.

Finally, we have to write U(k) = −1 + c V(k) and fix the base case by solving for c. Since U(0) = 1 = −1 + c V(0) = −1 + c, we get c = 2.

The overall solution is U(k) = 2k+1 − 1, hence

T(n) = 2log3(n)+1 − 1 = 2log2(n)/log2(3)+1 − 1 = 2 n1/log2(3) − 1.

user_21446690
Related