
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
September 15th, 2008, 06: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(n2) + 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, 09:11 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 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 15th, 2008, 11:53 PM  #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, 09:42 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Asymptotic lower/upper bounds for unconventional T(n)? Quote:
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, 03: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, 07: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, 06:16 AM  #7  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Asymptotic lower/upper bounds for unconventional T(n)? Quote:
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, 02: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:
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, 07:09 AM  #9  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 937 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Asymptotic lower/upper bounds for unconventional T(n)? Quote:
 
September 21st, 2008, 07: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:
Anyway, what's a more elegant method of solving this from t(m) = 2^m/2 ( t(m/2) + 2^m/2) ?  

Tags 
asymptotic, bounds, lower or upper, unconventional 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Upper and lower bounds theorems  p99410  Algebra  2  December 17th, 2013 03:08 PM 
Lower and upper bounds  will_hunting_math  Computer Science  13  April 6th, 2013 11:14 AM 
Asymptotic lower/upper bounds for T(n) [Master Theorem?]  Shaitan00  Applied Math  3  September 15th, 2008 05:59 AM 
Upper lower bounds  Kiranpreet  Algebra  4  April 1st, 2008 09:42 AM 
Upper and Lower Bounds of roots  roadnottaken  Algebra  7  August 11th, 2007 03:31 AM 