Hey everybody!
Really need some help cause I'm lost!
I need to find an asymptotically tight bound for this sum
http://img231.imageshack.us/img231/1606/32830911.jpg
, and I know u can't bound a sum, so I can't figure out a way to do it!! I'd REALLY appreciate if someone could explain to me (in the most simple way possible) what I need to do in a situation where I have a sum to bound)
THANK YOU!!!!
arcticM
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
and I know u can't bound a sum
Um, yes you can. For example, you can make a very rough bound: if you have a sum of j values that are each less than or equal to k, then their sum is less than or equal to j*k. You might be able to get a tighter bound, though -- going by the reasoning I just gave, you would say that 1+2+4+8+...+2^n <= (n+1)*2^n, which is more general than necessary -- a tighter bound would be 2*2^n. The sum actually equals 2*2^n - 1.
So you can, with very simple reasoning, find an upper bound for a sum -- but it might not be a tight upper bound -- it will give an asymptotic bound that is between O(1) and O(n) times the tightest possible.
To find a lower bound, you can use the same reasoning in the opposite direction: if you have a sum of j values that are each greater than or equal to l, then their sum is greater than or equal to j*l. So by that reasoning, you could say that 1+2+4+8+...+2^n >= n+1. That's pretty useless.
You can actually create a tighter lower bound (restricting yourself to dumb reasoning) by dropping the smaller elements from the sum. Let's drop half the elements from the sum: 2^(n/2) + 2^(n/2+1) + ... + 2^n >= ((n+1)/2)*2^(n/2). We get a tighter lower bound -- but not as tight as possible.
Try doing this reasoning to get upper and lower bounds for the problem you're given.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.