Solve: T(n) = T(n-2) + (n-1) ; T(0) = 0 and T(1) = 0 What I\'ve tried so far: T(

Question

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

What I've tried so far:

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

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

T(n+2)=T(n)+(3n+0)

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

T(n+4)=T(n+2)+(5n+5)

I just cannot figure out what to do.  Any help would be greatly appreciated.

T(n) = T(n-2) + (n-1) ; T(0) = 0 and T(1) = 0 What I've tried so far: T(n) = T(n-2) +(n-1) T(n+1) =T(n-1)+(2n-1) T(n+2)=T(n)+(3n+0) T(n+3)=T(n+1)+(4n+2) T(n+4)=T(n+2)+(5n+5) I just cannot figure out what to do. Any help would be greatly appreciated.

Explanation / Answer

T(1) = 1 and not 0. This is a typing mistake

This is a fibonacci series

I will give you the psuedocode

function fibonacci(int n)

{

if( n == 0)

return 0;

else if (n ==1)

return 1;

else

return ( fibonacci(n-1) + fibonacci(n-2));

}

Obserbve what we do in the function, it first has two base cases which correspond to the condition T(0) = 0 and T(1) = 1

the third case is the recursive statement which says that to calculate T(m) we calculate T(m-1) and T(m-2) and then add them up.

so for n = 2

it will call fibonacci (1) first

which will return 1

then it will call fibonacci (0)

which will return 0

so final value returned will be 1 + 0 = 1

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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