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

 Applied Math Applied Math Forum

 September 15th, 2008, 07:15 AM #1 Newbie   Joined: Sep 2008 Posts: 8 Thanks: 0 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,
 September 15th, 2008, 10:11 AM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Asymptotic lower/upper bounds for unconventional T(n)? Given some (tiny) positive epsilon and large enough n, n^(a + epsilon) > n^a * log n. x^1.05 > x log x for all x > 2 x 10^39, for example.
 September 16th, 2008, 12:53 AM #3 Newbie   Joined: Sep 2008 Posts: 8 Thanks: 0 Re: Asymptotic lower/upper bounds for unconventional T(n)? CRGreathouse: I don't see how that solves the question at hand - how can I apply that to either of my 2 problems? (sorry - still kind of new at this). Thanks,
September 16th, 2008, 10:42 AM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Asymptotic lower/upper bounds for unconventional T(n)?

Quote:
 Originally Posted by Shaitan00 CRGreathouse: I don't see how that solves the question at hand - how can I apply that to either of my 2 problems? (sorry - still kind of new at this).
It's a direct answer to the question of how you can make x log x into a simpler expression (one that the MT can solve). Replace x log x with x^(1 + eps) and use the master theorem as normal; the epsilon will remain in the result, and can be taken arbitrarily small (but positive). Don't use Theta, though, just O.

I mentioned an alternate solution on the other thread: lifting out the log(n) term and replacing with the log(m) upper bound. Think of it this way (using your example T(n) = 5T(n/5) + n log n):

T(m)
= 5T(m/5) + m log m
= 5(5T(m/25) + m/5 log (m/5)) + m log m
= 25T(m/25) + m log (m/5) + m log m
= 25(5T(m/125) + m/25 log (m/25)) + m log (m/5) + m log m
= 125T(m/125) + m log (m/25) + m log (m/5) + m log m
...
= m * Sum(i=1, log_2 m, log(m/5^i))
< m (log m * log_2 m)
= O(m log^2 m)

 September 18th, 2008, 04:41 PM #5 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Re: Asymptotic lower/upper bounds for unconventional T(n)? For a, at least, you can use a variable substitution (I'm not terribly fond of the Master Theorem, unless it directly applies...) I don't have time right now to go through it, but I'll get to it tonight or tomorrow morning. (The substitution is n=> 2^m...) Also, I'm new to this, and not sure if I'm doing it right... So we can see together.
 September 19th, 2008, 08:20 PM #6 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Re: Asymptotic lower/upper bounds for unconventional T(n)? The answer I'm getting (for part a) doesn't seem right... so it's very, very likely that one of my steps isn't valid... CRG can point it out if so... Also, the answer I got doesn't seem to make sense (it seems like it should grow faster than what my "solution" says) Anyway: T(n) = n^1/2 * T(n^1/2) + n Let 2^m = n (i.e. m= lgn [lg for log base 2]) T(2^m) = 2^(m/2)*T(2^m/2) + 2^m Let t(m) = T(2^m) (notice that t(m) = T(n) t(m) = 2^m/2 t(m/2) + 2^m (I'm not entirely sure about this step...) t(m) = 2^m/2 ( t(m/2) + 2^m/2) Now, since f(x) * O(g(x)) = O(f * g(x)), we can apply the master theorem to everything inside of the parenthesis: m^(lg1 + 1) = m^1 = m, which is asymptotically dominated by 2^m/2 t(m) = 2^m/2 (O(2^m/2)) = O(2^m) = Substitute back in n (and T(n), since they're the same function) to get: T(n) = O(n) I feel like the actual recursion should have a little more play, but I guess it is heavily dominated by n... But it really should have an effect. The first time I did it, I did it quickly and probably messed something up, but got n^3/2 for the answer, which makes a little more sense. Any thoughts?
September 20th, 2008, 07:16 AM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Asymptotic lower/upper bounds for unconventional T(n)?

Quote:
 Originally Posted by cknapp Any thoughts?
Intuitively, you're adding n, n^1/2, n^1/4, and so on, clearly dominated by the first term.

Those form n^1/2 * n^1/4 * n^1/8 * ... = n^(1/2 + 1/4 + 1/8 + 1/16 + ...) = n^1.

So the total complexity is O(n) -- in fact no more than 2n + O(sqrt(n)log(n)). Depending on how you handle the 'series', this could even be n + o(n).

September 20th, 2008, 03:21 PM   #8
Senior Member

Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 3

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

Quote:
Originally Posted by CRGreathouse
Quote:
 Originally Posted by cknapp Any thoughts?
Intuitively, you're adding n, n^1/2, n^1/4, and so on, clearly dominated by the first term.

Those form n^1/2 * n^1/4 * n^1/8 * ... = n^(1/2 + 1/4 + 1/8 + 1/16 + ...) = n^1.

So the total complexity is O(n) -- in fact no more than 2n + O(sqrt(n)log(n)). Depending on how you handle the 'series', this could even be n + o(n).
Oh, right, we did a similar example in class, and it came out as such. In my brain, it was a multiplication and not an addition.
So, then my technique was valid? I just meshed together some ideas from class and tried to avoid anything that seemed "illegal"... which, I guess, is how math works.

September 21st, 2008, 08:09 AM   #9
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Asymptotic lower/upper bounds for unconventional T(n)?

Quote:
 Originally Posted by cknapp Oh, right, we did a similar example in class, and it came out as such. In my brain, it was a multiplication and not an addition. So, then my technique was valid? I just meshed together some ideas from class and tried to avoid anything that seemed "illegal"... which, I guess, is how math works.
Your way seems fine, though you're using a pretty big hammer (Master Theorem) where I'm not sure it's needed.

September 21st, 2008, 08:35 AM   #10
Senior Member

Joined: Oct 2007
From: Chicago

Posts: 1,701
Thanks: 3

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

Yeah, I'm trying to get used to recurrences, and I don't particularly like the Master Theorem, but there are certainly instances where it seems much easier. I should know other

Quote:
 Originally Posted by CRGreathouse though you're using a pretty big hammer (Master Theorem) where I'm not sure it's needed.
"If brute force doesn't work, you aren't using enough of it."

Anyway, what's a more elegant method of solving this from t(m) = 2^m/2 ( t(m/2) + 2^m/2) ?

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post p99410 Algebra 2 December 17th, 2013 04:08 PM will_hunting_math Computer Science 13 April 6th, 2013 12:14 PM Shaitan00 Applied Math 3 September 15th, 2008 06:59 AM Kiranpreet Algebra 4 April 1st, 2008 10:42 AM roadnottaken Algebra 7 August 11th, 2007 04:31 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top