Results 1 to 2 of 2

Math Help - Asymptotic lower/upper bounds for unconventional T(n)?

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    11

    Question Asymptotic lower/upper bounds for unconventional T(n)?

    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.
    Thanks,
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member bkarpuz's Avatar
    Joined
    Sep 2008
    From
    R
    Posts
    481
    Thanks
    2

    Arrow

    For the first one, set a new variable k by k:=\ln(n),
    then n=\mathrm{e}^{k} and your system takes the form
    S(k)=\mathrm{e}^{k/2}S(k/2)+\mathrm{e}^{k},
    where S(k):=T(\mathrm{e}^{k}).
    You may also wish to set \ell=\log_{2}(k) to get
    R(\ell)=\mathrm{e}^{2^{\ell-1}}R(\ell-2)+\mathrm{e}^{2^{\ell}}.
    Do you think this is useful?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Upper and Lower Bounds
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 18th 2010, 09:49 PM
  2. Upper and Lower Bounds
    Posted in the Algebra Forum
    Replies: 5
    Last Post: March 11th 2010, 11:44 AM
  3. Upper and lower bounds help?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 5th 2010, 02:07 PM
  4. Replies: 0
    Last Post: September 15th 2008, 12:35 AM
  5. Greatest lower bounds and least upper bounds
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 31st 2008, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum