Recursive Equation
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: Recursive Equation

  1. #1
    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. #2
    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. #3
    Join Date
    Mar 2010
    Posts
    5

    Re: Recursive Equation

    Quote Originally Posted by nuzzle View Post
    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!

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Recursive Equation

    Quote Originally Posted by Lordofnazgul View Post
    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. #5
    Join Date
    Oct 2008
    Posts
    1,090

    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. #6
    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. #7
    Join Date
    Oct 2008
    Posts
    1,090

    Re: Recursive Equation

    Quote Originally Posted by Lordofnazgul View Post
    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. #8
    Join Date
    Apr 2010
    Posts
    1

    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center