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

1. ## 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,

2. 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?