-
March 27th, 2010, 11:11 AM
#1
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!
-
March 28th, 2010, 05:23 AM
#2
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.
-
March 29th, 2010, 09:28 AM
#3
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!
i have uploaded here how i made the exercise:
http://rapidshare.com/files/369564403/08.PDF.html
what do you think about it??
thank you!
-
March 29th, 2010, 11:37 PM
#4
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.
-
March 30th, 2010, 06:04 AM
#5
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).
-
March 30th, 2010, 11:44 AM
#6
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!
-
March 31st, 2010, 08:06 AM
#7
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 ? ).
-
April 3rd, 2010, 06:50 PM
#8
Recursive algorithm
Hi everybdoy ı need your help about recursion algorithm in mathematica.
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|