Hey everybody!
Really need some help cause I'm lost!
I need to find an asymptotically tight bound for this sum
, 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)

8 Years
Discussion Span
Last Post by Rashakil Fol

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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.