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

#1 zeion  Icon User is offline

  • New D.I.C Head

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

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

Posted 23 September 2012 - 05:31 PM

Attached Image

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  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • 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).
Was This Post Helpful? 2
  • +
  • -

#3 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2118
  • View blog
  • Posts: 3,244
  • Joined: 21-June 11

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

Posted 25 September 2012 - 12:14 AM

View Postmojo666, 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.
Was This Post Helpful? 2
  • +
  • -

#4 zeion  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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

View Postsepp2k, on 25 September 2012 - 12:14 AM, said:

View Postmojo666, 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

Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10596
  • View blog
  • Posts: 39,259
  • 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.
Was This Post Helpful? 1
  • +
  • -

#6 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • 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?
Was This Post Helpful? 2
  • +
  • -

Page 1 of 1