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

[Shaitan00]

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 completely 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,

 

[lippyka]

The master theorem is a useful tool for solving recurrence relations that can be expressed in the form T(n) = aT(n/b) + cn^k, where a ≥ 1, b > 1, and k ≥ 0. However, it cannot be used to solve recurrence relations which don't fit this form. For the first problem, a) T(n) = n^1/2 * T(n^1/2) + n, we can use the substitution method. This involves replacing the given recurrence relation with a new one and then solving it using the master theorem. In this case, we can let T(n) = U(n) and T(n^1/2) = U(n^1/2). Then, the recurrence relation becomes U(n) = U(n^1/2)+n. By the master theorem, this will have an upper bound of O(n^log_2(3)).For the second problem, b) T(n) = T(n-2) + 2*log(n), we can use the iteration method. This involves solving the given recurrence relation by iteratively substituting values for n until the result is found. In this case, we can start by substituting n=2. The recurrence relation becomes T(2) = T(0) + 2*log(2), or T(2) = 0 + 2*1 = 2. We can then substitute n=4, which gives us T(4) = T(2) + 2*log(4) = 2 + 2*2 = 6. We can continue this process, and eventually find that the upper bound for T(n) is O(n).