8 Replies - 2547 Views - Last Post: 04 October 2012 - 11:41 AM

#1 zeion  Icon User is offline

  • New D.I.C Head

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

Summation bound proof (with big O notation), need to show convergence?

Posted 01 October 2012 - 05:59 PM

Attached Image

Hi,

I'm not sure how to go about doing this. Do I need to use induction? Or do I need to prove that the series converges hence bounded by some horizontal line?
Is This A Good Question/Topic? 0
  • +

Replies To: Summation bound proof (with big O notation), need to show convergence?

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 730
  • Joined: 27-June 09

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 02 October 2012 - 08:54 AM

If you prove that it converges, you are pretty much done. You can do this by induction, calculus, or any other valid method.
Was This Post Helpful? 2
  • +
  • -

#3 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3168
  • View blog
  • Posts: 9,581
  • Joined: 05-May 12

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 03 October 2012 - 08:45 AM

Okay, now I'm the one who needs help understanding the question.

How can that be an O(1) operation if I need to get the sum of N items? Isn't ranging over a set of values an O(n) operation? So if I had a database with 1 million rows, and another database with just 1 row, then the cost of getting the sum of the rows is the same if it were O(1)? I don't think so. I think that the time for summing all the rows would be dependent on the number of rows.

Additionally, isn't computing x^y also an O(n) operation since the naive implementation of x^y == x * x * x ... * x (where x is multiplied by itself y times)?

Or is the idea that the result of the summation approaches a constant value? (It's been a while, but it looks like it'll approach the value 1.) So given that we know what the result will be, then we can just use the end value? But that just doesn't work if the upper limit of n for the summation is not big enough.

Let's say for example that formula was used to compute your the sum of the ratio of your bonuses to your income over the number of years that you've worked for a company. (Sounds like a disincentive to work there long, but still for arguments sake.) The first year you work, you get 1/2 of your income as a bonus; the second year you get 1/4, etc. Since the sum of the limit approach 1, can you at the end of your first year tell your boss that he should just give you a 100% bonus because the summation approaches 1?

Help?!?!

This post has been edited by Skydiver: 03 October 2012 - 08:46 AM

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2013
  • View blog
  • Posts: 3,038
  • Joined: 21-June 11

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 03 October 2012 - 09:27 AM

@Skydiver:

This question has nothing to do with runtime (or for that matter computation).

Saying "function f is in O(1)" does not mean that the runtime of calculating that function is in O(1), it just means that f is in O(1), i.e. that is bounded by a constant.

This post has been edited by sepp2k: 03 October 2012 - 09:28 AM

Was This Post Helpful? 2
  • +
  • -

#5 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3168
  • View blog
  • Posts: 9,581
  • Joined: 05-May 12

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 03 October 2012 - 09:34 AM

Ah! Thanks. That clears things up dramatically.
Was This Post Helpful? 0
  • +
  • -

#6 zeion  Icon User is offline

  • New D.I.C Head

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

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 03 October 2012 - 03:38 PM

I haven't worked with series in a while. Can I use the ratio test to show convergence?
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10184
  • View blog
  • Posts: 37,599
  • Joined: 27-December 08

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 04 October 2012 - 07:06 AM

You could use the ratio test.
Was This Post Helpful? 0
  • +
  • -

#8 Dogstopper  Icon User is online

  • The Ninjaducky
  • member icon



Reputation: 2857
  • View blog
  • Posts: 10,962
  • Joined: 15-July 08

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 04 October 2012 - 07:58 AM

Skydiver, this is a good question. Some things have a LATENCY of O(n) and have an AVERAGE of O(1). For example, hashtables come in many implementations. Let's use a LinearProbingHashtable for example. You implement this by hashing the keys and modding the hash by the length of the array to find the index to place it in. This is, in general O(1) for ANY length list. However, what happens if you have a bad hashing scheme that causes a lot of collisions?

Due to the way the LinearProbingHashtable works, it probes linearly at that point until there is a free spot available. Which then leads to the next part - the load factor. It is a factor that determines the maximum space that can be filled (generally .7). When 70% of the array is filled, you must increase the size of the array (not by kx, but by kx +1) and reads all the hashes, which easily approaches O(N) time. This means that actually, that O(1) is not the true Big Oh --- just the average. The big Oh is actually O(1 + k/n) where k is the number of elements and n is the number of bins.
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10184
  • View blog
  • Posts: 37,599
  • Joined: 27-December 08

Re: Summation bound proof (with big O notation), need to show convergence?

Posted 04 October 2012 - 11:41 AM

Also, Skydiver, it goes back to the definition of Big-O:

Quote

A function f(n) is Big-O g(n) if and only if there exist constants C and k (both positive integers) such that |f(x)| <= C * |g(x)| for all x >= k, x is a positive integer.


So if the series converges to a value, then it is bounded by some constant. If g(n) = 1 and f(n) converges to 5 (as an example), then f(n) is still O(g(n)) because C can take on the value of any integer >= 5.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1