1. Not finding help here? Sign up for a free 30min 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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?

Similar Discussions: Asymptotic lower/upper bounds for T(n) [Master Theorem?]
  1. Some T/F on matrices (Replies: 0)

  2. Master Theorem (Replies: 0)

  3. Upper and lower bounds (Replies: 0)

  4. Cauchy's theorem (Replies: 0)