Comp.145  January 1997  Dr. A.J. Mestel

Example on recurrence relations

T_{n} is the amount of CPU needed to perform a certain task for a system of size measured by n.

If algorithm A is used, T_{n} satisfies the recurrence relation

T_{n+2} − 3T_{n+1} + 2T_{n} = 1

while if algorithm B is used, T_{n} satisfies

T_{n+2} − \frac{5}{2}T_{n+1} + T_{n} = 1 .

Find all possible solutions for T_{n} in each case. Show that for large values of n:

(i) If T_{0} = 3 and T_{1} = 4 then algorithm A is preferable. (ii) If T_{0} = 3 and T_{1} = 6 then algorithm B is preferable.