0
$\begingroup$

This question already has an answer here:

I have a recurrence relation of the form given below (taken from Analysis of Algorithms - An Active Learning Approach by Jeffrey J. McConnell):

$T(n) = 2T(n - 2) - 15 $

$T(2) = T(1) = 40 $

I am asked to find a closed-form for the recurrence relation i.e. to remove the recursive nature of the equations.

Working: My professor said it would be easier if you could see the patterns taking form if you expand the equations up to a few steps. So,

$T(n) = 2T(n - 2) - 15 $

$= 2(2T(n - 4) - 15) - 15$

$= 4T(n - 4) - 2\times 15 - 15 $

$ = 4(2T(n - 6) - 15) - 2\times15 - 15$

$ = 8T(n - 6) - 4 \times 15 - 2\times15 - 15$

I observe that the coefficient of $T$ in each step is a power of 2. The size of the problem during each recursive call decreases by 2. Also, there is a -15 term multiplied by the next power of 2.

But I am stuck here and do not know how to proceed further i.e. to obtain a closed-form. The book says to consider cases when $n$ is odd and even. But I do not get it at all. Any help would be appreciated.

Note: The material hasn't covered advanced topics like solving recurrence relations yet.

$\endgroup$

marked as duplicate by dkaeae, xskxzr, Evil, Discrete lizard Jul 24 at 10:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

It might be helpful if N is assigned a range of values from 1 to say 7 and evaluated till the recursion end is reached. also summing together terms with 15 multiples separately and 40 multiple separately, because they are the building blocks from the base case and recursion.

T(1) = 40.

T(2) = 40.

....

T(6) = 2 * ( 2 * 40 - 15 ) - 15 = 4 * 40 - 3 * 15

T(7) = 2 * ( 2 * ( 2 * 40 - 15 ) -15 ) - 15 = 8 * 40 - 7 * 15

i think this can help to find the closed form. But i am not an expert in this area.

$\endgroup$
0
$\begingroup$

Hint: Consider $Q(N) = T(N) - 15$. Derive a recurrence relation for $Q(N)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.