[zeion]

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?

[mojo666]

If you prove that it converges, you are pretty much done. You can do this by induction, calculus, or any other valid method.

[Skydiver]

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

[sepp2k]

@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

[Skydiver]

Ah! Thanks. That clears things up dramatically.

[zeion]

I haven't worked with series in a while. Can I use the ratio test to show convergence?

[macosxnerd101]

You could use the ratio test.

[Dogstopper]

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.

[macosxnerd101]

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.