I couldn't find a solution to my question since usually the solution (in big Os terms) is what's asked, but not the unrolled recurrence. If that was asked already just tell me and I'll delete.
I had this question in my Algorithms and Data Structures test in uni, and I've been banging my head on this one for a while. Mostly because I don't get how I'd come to the right answer.
I have the following relation:
T(1)=2
T(n)=2T(n-1)+2 for n>=2
The answers are:
1. T(n)= 2^n+1 -2
2. T(n)= none of the answers are correct
3. T(n)= 1/2n(n+1)-1
4. T(n)= 2^n+1 -2-n
5. T(n)= n+ (-1)^n
This is what I tried:
T(1)=2
T(n)=2T(n-1)+2 -> T(n-1) = T(n-2)+2
=2T(n-2)+2+2
=2T(n-2)+4 -> T(n-2) = T(n-3)+3
=2T(n-3)+2+4
=2T(n-3)+6 so then -> 2T(n-k)+2k and if n=k 2T(n-n)+2n -> 2T(0)+2n
BUT I don't have the T(0) case. Also, this method would ultimately bring me to know the big O solution, although it's not what I'm trying to find now.
Would anyone be kind enough to explain me the right method to get to the right answer?
Thank you.
Don't unroll the answers, just check them.
So for each of the possible answers check if T(1)=2, and if substituting the given T(n) gives equality for T(n)=2T(n-1)+2. So for the first answer T(1)=2^(n+1)-2=4-2=2 (as it should be) and:
T(n) =?= 2*T(n)+2
2^(n+1)-2 =?= 2*(2^(n)-2)+2
Using the simply =?= to mean the equality to check. Simplify both sides leads to:
2^(n+1)-2 =?= 2*2^(n)-2
The rest I leave to you