My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
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(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,
Shaitan00 is offline  
 
September 15th, 2008, 09:11 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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,
Shaitan00 is offline  
September 16th, 2008, 09:42 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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)
CRGreathouse is offline  
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.
cknapp is offline  
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?
cknapp is offline  
September 20th, 2008, 06:16 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
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).
CRGreathouse is offline  
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:
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.
cknapp is offline  
September 21st, 2008, 07:09 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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:
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) ?
cknapp is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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





Copyright © 2018 My Math Forum. All rights reserved.