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