CODEWITHSUNDEEP
algorithmrecursionbig-orelationrecurrence
Tommaso Pellegrini
Tommaso Pellegrini

Reputation: 55

Unrolling recursive recurrence relations

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.

Upvotes: 0

Views: 1958

Answers (5)

RARE Kpop Manifesto
RARE Kpop Manifesto

Reputation: 2915

For the progression, it helps to think of the chain like :

126 

=  111 111 0 (base-2)

=  2 * (2 * (2 * (2 * (2 * (2 * (+ 1) + 1) + 1) + 1) + 1) + 1) + 0

=  2 * (2 * (2 * \
  (2 * (2 * (2 * ( + 1) + 1) + 1) \
                   + 1) + 1) + 1) + 0

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58369

T(n)=2T(n-1)+2 is equivalent to T(n)+2 = 2(T(n-1)+2).

So T(n)+2 = 2^(n-1)(T(1)+2) = 2^(n-1)*4 = 2^(n+1). Thus T(n) = 2^(n+1)-2.

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59323

The easy way is to notice that it's exponential, and then just check the two exponential answers...

But if you want to unroll it, then you get:

T(n) = 2 + 2T(n-1)
     = 2 + 4 + 4T(n-2)
     = 2 + 4 + 8 + 8T(n-3)
     = 2 + 4 + 8 + ... + 2^(n-1)T(1)
     = 2 + 4 + 8 + ... + 2^n

and then you recognize the progression and do:

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

Upvotes: 0

Hans Olsson
Hans Olsson

Reputation: 12527

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

Upvotes: 1

Yash Shah
Yash Shah

Reputation: 1654

This problem is similar to https://cs.stackexchange.com/questions/18900/how-do-i-show-tn-2tn-1-k-is-o2n

You might understand how to solve this too...

Upvotes: 0

Related Questions