Recursive Equation
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Mar 2010
Posts
5

## Recursive Equation

Hello! i'm from Italy, and i'm trying to solve this equation:

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

my result is that the big theta notation of this equation is Θ(2^n) and the big O notation is O(2^n) * (n)

but i think that i made something wrong. Can someone explain me how to calculate the tree main landau symbols of this equation? (O, Ω and Θ)? i need some help because i have the test not too far away. Thank you!

2. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Recursive Equation

Salve!

Have you managed to solve the equation or have you been using some other procedure to get at the complexity measures you're suggesting?
Last edited by nuzzle; March 29th, 2010 at 02:43 AM.

3. Junior Member
Join Date
Mar 2010
Posts
5

## Re: Recursive Equation

Originally Posted by nuzzle
Salve!

Have you managed to solve the equation or have you been using some other procedure to get at the complexity measures you're suggesting?
Hello!

http://rapidshare.com/files/369564403/08.PDF.html

what do you think about it??
thank you!

4. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Recursive Equation

Originally Posted by Lordofnazgul
what do you think about it??
I haven't worked much with recurrance relations and I was hoping to be able to solve this one formally but unfortunately I haven't been very successful.

Regarding your solution it looks like you've come up with a Fibonacci tree but that corresponds to only this part of the equation doesn't it?

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

What I do know is that a Fibonacci tree grows almost as fast as a binary three corresponding to this equation,

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

And both have exponential growth so it should be O(c^n) for both.

The question is what happens when you add the n term? I have been able to solve this,

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

and according to my results the dominant term becomes 3*2^n when n grows big. This also means your equation has exponential growth too (because it's bound between two equations with exponential growth), like

T(n) = T(n - 1) + T(n - 2) (lower bound)
T(n) = T(n - 1) + T(n - 2) + n (your equation)
T(n) = 2*T(n-1) + n (upper bound)

So I'm pretty sure Big-O for your equation is O(c^n). I come back if I manage to actually solve it. The problem I'm having is that when I solve it as a second order difference equation the solution I get doesn't correspond to the values you expect when you use the formula as a recurrence relation. I'll try to figure out why this is so.
Last edited by nuzzle; March 30th, 2010 at 10:46 AM.

5. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Recursive Equation

this sort of linear recursive equation are usually solved by summing their z transforms:

sum{n,2,+inf} T[n]/z^n = sum{n,2,+inf} T[n-1]/z^n + sum{n,2,+inf} T[n-2]/z^n + sum{n,2,+inf}n/z^n

then, we have

sum{n,2,+inf} T[n-1]/z^n = ( T[1]/z + sum{n,2,+inf} T[n]/z^n ) / z

and

sum{n,2,+inf} T[n-2]/z^n = ( T[0] + T[1]/z + sum{n,2,+inf} T[n]/z^n ) / z^2

and

sum{n,2,+inf}n/z^n = sum{n,1,+inf}n/z^n - 1/z = z/(z-1)^2 - 1/z

therefore

sum{n,2,+inf} T[n]/z^n ( 1 - 1/z - 1/z^2 )= T[1]/z^2 + T[0]/z^2 + T[1]/z^3 + z/(z-1)^2 - 1/z

that is ( calling A:=T[0] and B:=T[1] for clarity )

sum{n,0,+inf} T[n]/z^n = A + B/z + ( (A+B)/z^2 + B/z^3 + z/(z-1)^2 - 1/z ) / ( 1 - 1/z - 1/z^2 )

finally, the not difficult but very boring part: we need to calculate the Laurent expansion of the right hand side... I have no time at the moment, so I simply computed the expansion in Wolfram Mathematica; it gives me

((1/2 (1 - Sqrt[5]))^n (-5 + 3 Sqrt[5] + A + Sqrt[5] A - 2 B) + (1/2 (1 + Sqrt[5]))^n (5 + 3 Sqrt[5] + (-1 + Sqrt[5]) A + 2 B))/(2 Sqrt[5]) - n - 3

which seems correct (of course A,B,n integers and n>=2 ). Indeed, as nuzzle said, it's O(c^n).

6. Junior Member
Join Date
Mar 2010
Posts
5

## Re: Recursive Equation

wow thank you to both of you! the only thing is that i have never made the z-transforms and they seems a little bit complicated! i would try to solve them with an easier method, but i don't understand how i can do... because the other exercises that my teacher gave us were much easier, but this one is more difficult... isn't there another way to solve them?? for example with the tree (as i did in the file i posted), or just substitution would be better! thank you!

7. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Recursive Equation

Originally Posted by Lordofnazgul
isn't there another way to solve them??
well, the z transform is the most systematic way of solving these equations (more specifically, when you'll study a bit of complex analisys you'll immediately recognize that the "n" term in your recurrence equation add an holomorphic term to the z transform; this basically means that the result can be "somehow" computed this way ... )

but there are certainly other ways of solving it. For example, you can "linearize" your recurrence equation by representing the recurrence step as a linear operator in a suitable vector space. Then, the problem essentially reduces to a matrix diagonalization
(an hint: how does the quadruple (T[n+1],T[n],n,1) get transformed by the recurrence step ? ).

8. Junior Member
Join Date
Apr 2010
Posts
1

## Recursive algorithm

Question is ı could not get any result when ı coded below equation. it is not stoping.

Equation is

S[n1_,n2_,p_,t_]:=n1/(2*n1-1)(S[n1-1,n2,p,t]-(n1-1)S[n1-2,n2,p,t])-n2/(2*n2-1)(S[n1,n2-1,p,t]-(n2-1)S[n1,n2-2,p,t])

here the S[0,0,p,t]=p*t (I just write simple one here)
-1<t<1
for examlple S[2,2,1,0.5]=?
can you code it in mathematica.
Thanks

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•