# Need help with this question (big-O bounds with sigma summation)

Page 1 of 1

## 5 Replies - 5850 Views - Last Post: 26 September 2012 - 11:21 PM

### #1 zeion

Reputation: 0
• Posts: 20
• Joined: 23-September 12

# Need help with this question (big-O bounds with sigma summation)

Posted 23 September 2012 - 05:31 PM

Thanks

Is it a problem with the induction proof? I'm not sure how to start.
Is This A Good Question/Topic? 0

## Replies To: Need help with this question (big-O bounds with sigma summation)

### #2 mojo666

Reputation: 397
• Posts: 857
• Joined: 27-June 09

## Re: Need help with this question (big-O bounds with sigma summation)

Posted 24 September 2012 - 11:58 AM

Well, the sum of the first n integers is (n^2+n)/2 which is O(n^2).

### #3 sepp2k

• D.I.C Lover

Reputation: 2298
• Posts: 3,557
• Joined: 21-June 11

## Re: Need help with this question (big-O bounds with sigma summation)

Posted 25 September 2012 - 12:14 AM

mojo666, on 24 September 2012 - 08:58 PM, said:

Well, the sum of the first n integers is (n^2+n)/2 which is O(n^2).

"The problem with the proof is that it proofs something that isn't true" isn't a very satisfying answer though. That's like if you ask someone to help you spot a bug in your program and he says "Well, clearly the problem with your program is that it produces the wrong output and/or crashes when it's not supposed to".

@zeion Does the following sentence make sense to you "This function is in O(n) for small n, and in only O(n^2) for large n"? If yes, you need to more closely think about what big-Oh notation means. If no, you should try to formulate why it doesn't make sense. Hopefully this will make you see the flaw in the proof.

### #4 zeion

Reputation: 0
• Posts: 20
• Joined: 23-September 12

## Re: Need help with this question (big-O bounds with sigma summation)

Posted 26 September 2012 - 05:41 PM

sepp2k, on 25 September 2012 - 12:14 AM, said:

mojo666, on 24 September 2012 - 08:58 PM, said:

Well, the sum of the first n integers is (n^2+n)/2 which is O(n^2).

"The problem with the proof is that it proofs something that isn't true" isn't a very satisfying answer though. That's like if you ask someone to help you spot a bug in your program and he says "Well, clearly the problem with your program is that it produces the wrong output and/or crashes when it's not supposed to".

@zeion Does the following sentence make sense to you "This function is in O(n) for small n, and in only O(n^2) for large n"? If yes, you need to more closely think about what big-Oh notation means. If no, you should try to formulate why it doesn't make sense. Hopefully this will make you see the flaw in the proof.

I'm guessing it's a flaw with the "Assume P(n)"?
If we assume P(n) then we assume that summing the first n integer is O(n) by the base case, which is false.. or is that still not satisfying?

This post has been edited by macosxnerd101: 26 September 2012 - 05:58 PM
Reason for edit:: Removed multipost

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11765
• Posts: 44,209
• Joined: 27-December 08

## Re: Need help with this question (big-O bounds with sigma summation)

Posted 26 September 2012 - 06:01 PM

mojo666 summed it up pretty well. You are dealing with the sum of a geometric series. For the first n elements, the sum is n(n+1)/2. So how can it be O(n)? Remember that part of the definition of Big-O includes: for all elements x >= k, such that x is a positive integer. In other words, we are dealing with the long-term growth.

### #6 mojo666

Reputation: 397
• Posts: 857
• Joined: 27-June 09

## Re: Need help with this question (big-O bounds with sigma summation)

Posted 26 September 2012 - 11:21 PM

Well, my statement was just to give him a simple equation to substitute in place of all the sums. It was just meant as a starting point. I know certain professors may find it sufficient to end there, but many require more work. The logic of the argument given is mostly valid, so like sepp pointed out, it is not enough to say "I got a different answer through a different method". You still need to figure out which method is correct. This is actually one of those tricky proofs where the operations are sound, but they violate a fundamental definition.

Your intuition is correct, zeoin. The statement P(n), which you are trying to prove, is awkward to begin with. The important thing to note is that in induction, the "n" in P(n) refers to one particular value. It can be any value, but it is just one value. Induction tries to prove P(n) is true for all values one "n" at a time. So, our equation (n^2+n)/2 is also one particular value. Does it make any sense to say a particular value is linear (another way of saying O(n))?
2 is linear
5 is linear
978327980 is linear

Big O is used to describe functions, not values. Since functions are applied to any value, part of big O's definition is that the necessary relations must hold for all n. Thus, Big O and the inductive step are using different definitions of n.

written out more formally P says
P(n) := {for constants k, n_0; sum(1 to n)<=k*n for all n>n_0 }

So what do you notice when you try to test P(1), P(5), ect? Is P true? Is it even coherent?