Results 1 to 4 of 4

Math Help - recurrences

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    10

    Question recurrences

    trying to make sure i'm doing this right...

    solve the recurrence in theta notation
    assume base case T(x) = 1 for x <= 5

    for T(n) = 4T(n/5) + n , is the answer T(n) = Theta(2n) ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by inneedofhelp View Post
    trying to make sure i'm doing this right...

    solve the recurrence in theta notation
    assume base case T(x) = 1 for x <= 5

    for T(n) = 4T(n/5) + n , is the answer T(n) = Theta(2n) ?
    First of all T(n) = \Theta (2n) is the same thing as T(n) = \Theta (n).

    Now:

    <br />
T(n) = 4 + \sum_{k=0}^{\lfloor log_5(n)-1 \rfloor } n(4/5)^k<br />

    Which is obviously \Theta (5n)=\Theta (n)

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2007
    Posts
    10
    ok, so if I have

    T(n) = T(n-3) + n^3

    then i'll have

    n^3 + (n-3)^3 + (n-6)^3 + (n-9)^3 + ... + 1^3

    so

    I'll have n-3 terms and max of n^3 at each one, so is this Theta(n^4) ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by inneedofhelp View Post
    ok, so if I have

    T(n) = T(n-3) + n^3

    then i'll have

    n^3 + (n-3)^3 + (n-6)^3 + (n-9)^3 + ... + 1^3

    so

    I'll have n-3 terms and max of n^3 at each one, so is this Theta(n^4) ?
    Yes (assuming you have suitable initial conditions), though I'm note sure the explanation of why its \Theta (n^4) is acceptable. I would use upper and lower bounds derived from an integral approximation to the sum.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solve the following linear recurrences.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 13th 2011, 01:01 AM
  2. Solve the following linear recurrences.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 12th 2011, 06:21 PM
  3. Recursion Trees with Recurrences
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2010, 04:20 PM
  4. recurrences
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 22nd 2010, 12:02 PM
  5. recurrences
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 26th 2008, 10:29 AM

Search Tags


/mathhelpforum @mathhelpforum