Results 1 to 5 of 5
Like Tree2Thanks
  • 2 Post By HallsofIvy

Math Help - Recurrence Relations

  1. #1
    Newbie
    Joined
    Apr 2013
    From
    Germany
    Posts
    14

    Recurrence Relations

    H!
    I have to solve the following recurrence relations:
    (a) T(n)=sqrt(2)*T(n/2)+lgn
    (b) T(n)=3*T(n/4)+nlgn
    (c) T(n) 3*T(n/3)+n/2
    (d) T(n)=5*T(n/2)+Θ(n)
    (e) T(n)=9*T(n/3)+O(n^2)
    Could you tell me if my results are right???
    Using the master theorem I found:
    (a)T(n)=Θ(sqrt(n))
    (b)T(n)=Θ(nlgn)
    (c)T(n)=Θ(nlgn)
    (d)T(n)=Θ(n^(log(2)5)
    (e)T(n)=Θ(n^2*lgn)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,259
    Thanks
    1800

    Re: Recurrence Relations

    What does "Θ" mean?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2013
    From
    Germany
    Posts
    14

    Re: Recurrence Relations

    f(n)=Θ(g(n)) \Rightarrow \exists c_{1},c_{2},n_{0}>0: \forall n\geq n_{0}, c_{1}g(n)\leq f(n)\leq c_{2}g(n)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,259
    Thanks
    1800

    Re: Recurrence Relations

    Okay, that is the "order" relation. I would use just o(g(n)).

    But if you are only saying, for example, that T(n) is "of the order of square root of n", you certainly have not SOLVED the equation,
    Thanks from topsquark and mathmari
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2013
    From
    Germany
    Posts
    14

    Re: Recurrence Relations

    And are the orders that I found right??
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 2nd 2012, 11:50 PM
  2. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  3. recurrence relations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 19th 2008, 10:08 PM
  4. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 14th 2008, 07:45 PM
  5. help with recurrence relations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 11th 2008, 06:07 PM

Search Tags


/mathhelpforum @mathhelpforum