I am stuck on this problem. I don\'t know what to do. I\'ve looked at doing back

Question

I am stuck on this problem. I don't know what to do. I've looked at doing backward substitution and forward substitution, but I cannot get past the substitution part. Could someone work this out in detail and explain what they are doing for every step. I realy need to understand how this works and not just an answer. Thanks much.

Solve: T(n)=T(n-2)+(n-1) ; T(0) = 0 and T(1) = 0

What I tried to do:

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

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

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

........

T(n-i) = T(n-i)+(-i)+.............+(n-i-1)+(n-i+0)+n

// I am pretty sure that it is this step where I am getting lost at. Five star for a well explained answer.

Explanation / Answer

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

T(n - 2) = T(n - 4) + (n - 3)

T(n - 4) = T(n - 6) + (n - 5)

..

..

..

now , putting the value of T(n - 2) in the right hand side..

we get,

T(n) = T(n - 4) + (n - 3) + (n - 1)

now , putting the value of T(n - 4) in the right hand side..

we get,

T(n) = T(n - 6) + (n - 5) + (n - 3) + (n - 1)

Again, recursively puttting the value of T(n - r) in the RHS, finally we get

T(n) = T(0) + 1 + 3 + 5 + 7 + .......... + (n - 1)

T(n) = 0 + 1 + 3 + 5 + 7 + ......... + (n - 1)

T(n) = 1 + 3 + 5 + 7 + ......... + (n - 1)

This is the sum of first n / 2 odd numbers

so,

T(n) = 2^(n / 2)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.