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 unconventional T(n)?

  1. Sep 15, 2008 #1
    Similarily to my previous post, 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 unconventional form I am at a loss to see how to solve the problem.

    For example - I am used to seeing T(n) = aT(n/b) + cn^k, however I am trying to solve two problems are do not conform to this format, specifically:

    a) T(n) = n^1/2 * T(n^1/2) + n
    b) T(n) = T(n-2) + 2*log(n)

    Both of these questions have me completly stumped...
    I did some reading/research and the typical answer I get is that to determine the upper bounds of a complex relationship you upper bound the complex expressions by simpler expression... This leaves me rather lost... Can anyone maybe help point me in the right direction? What kind of "simpler expression" could I use to help resolve these problems? Do I need to use the Master Theorem?

    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?