Guides on solving this recurrence relation equation?

[oslon]

T(n)=c if n=1 =2T(n-1)+d if n>1 Find the value of T(n) and thus the time complexity. My attempt at it got stuck. T(n)=4T(n-2)+3d T(n)=8T(n-3)+7d .. .. .. T(n)=8T(n-k)+7d It can't be solved further.

[Andre Oosthuizen]

Quote:

It can't be solved further

This does not help us in any way or format, why can it not be solved further, did it freeze, were there an error etc. etc.

[jeron1]

Start writing things out more fully then look for the pattern in terms of n .

T(1) = c

T(2) = 2T(1) + d
T(2) = 2c + d -------- take this
|
T(3) = 2T(2) + d |
|
____________| and put it here
|
/------\
T(3) = 2(2c + d) + d
T(3) = 4c + 2d + d
T(3) = 4c + 3d

T(4) = 2T(3) + d
T(4) = 2(4c + 3d) + d
T(4) = 8c + 6d + d
T(4) = 8c + 7d

T(5) = 2T(4) + d
T(5) = 2(8c + 7d) + d
T(5) = 16c + 14d + d
T(5) = 16c + 15d

"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment "Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst "I don't drink any more... then again, I don't drink any less." - Mike Mullikins uncle

[jschell]

Googling suggests that time complexity requires 'code'. So as a starting point doesn't one need to write the recursive function first?

[Marc Antoine Froger]

Maybe I didn't understand completely your question, but to me, your function T can be written like this : For any Positive non null integer n => T(n) = ( c + d ) * ( 2^( n - 1 ) ) - d It works also with n = 1 since T(1) becomes ( c + d ) * (2^0) - d => c + d - d => c