Recurrence Equation for algorithm

Question

I'm pretty new to recurrence equation concepts, need help with following algorithm

G(n)
Require: A positive integer n.
if n <= 1 then
return n
else
return 5*g(n - 1) - 6* g(n- 2)
end if

I came up with following recurrence equation for above :

T(n) = n, if n<=1,
T(n) = 5*T(n-1) - 6.T(n-2), if n>1

Is this correct, I also have to setup a recurrence for the number of multiplications performed by this algorithm. Please help.

Answer 1

The recurrence relation that you have built here is correct. Its basically you writing a problem in form of some smaller sub-problem.

Now for the number of multiplications. Keep 2 things in mind.

1. Number of steps you need to go down in the recurrence relation to reach the base case (n<=1 in this case).
2. Number of operation in each case.

Now for your recurrence.

T(n) = n, if n<=1

T(n) = 5*T(n-1) - 6.T(n-2), if n>1

You have a recursion that changes a problem to two sub problems at each step and at each step the value of n decreases by 1

T (n) = 5*T(n-1) - 6*T(n-2) T (n-1) = 5*T(n-2) - 6*T(n-3)

So n steps each time branching into 2 sub problems so you will have 2 * 2 * ... 2 (O(n) time) So there are 2^n steps in your problem approximately hence O(2^n) And each step has 2 multiplication and one subtraction.

A recurrence for number of multiplications will be like this

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

So the number of multiplication will be approximately ( 2^n )*2.