1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Asymptotic lower/upper bounds for T(n) [Master Theorem?]

  1. Sep 15, 2008 #1
    I am trying to find out how to solve the lower/upper bounds for a given T(n) - the book I have been reading refers to using the Master Theorem which I seem to be able to apply in the standard case, however when the T(n) is non-standard I am at a loss to see how to solve the problem.

    For example, with T(n) = 3T(n/2) + n^1/2 I know that a=3, b=2, k=1/2 so T(n) = O (n^log1.58) (using the standard Master Theorem approach).

    But now I am looking into solving the following problem:
    T(n) = 5T(n/5) + nlogn

    In this case f(n) = n*log(n) (not of the form n^k) and I am not sure how to evaluate this using either the Master Theorem (or any other valid method) - somehow I need to determine if
    Anyone have any clues?

    Any help would be much appreciated.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted