Big O notation confusion
Page 1 of 17 Replies  6206 Views  Last Post: 12 May 2013  08:28 PM
#1
Big O notation confusion
Posted 24 June 2010  10:56 PM
Looking at the algorithm and how it's performed, it looks to be closely related to n*pi(sqrt(n)) (where pi(n) is the primecounting function; i.e. the number of primes less than n). That's not even quadratic, let alone exponential (observation shows it to be close to n^1.3, actually).
Can someone please help me with this major point of confusion?
Replies To: Big O notation confusion
#2
Re: Big O notation confusion
Posted 24 June 2010  11:04 PM
#3
Re: Big O notation confusion
Posted 24 June 2010  11:16 PM
macosxnerd101, on 24 June 2010  10:04 PM, said:
I guess I didn't make this part clear. The "pi" I wrote is not the constant 3.14159... It represents the primecounting function. When I write pi(sqrt(n)) I'm saying "The number of primes less than the square root of n." Feel free to take a look at this wikipedia page if you're still confused: http://en.wikipedia....unting_function
But excluding that tidbit, I understand your reasoning. My question is then why do we choose to bound it with an exponential? If it can be represented by n^(3/2), why not bound it by something like n^2? That's always above it too (as long as n is greater than 1), right?
This post has been edited by starving_mathematician: 24 June 2010  11:19 PM
#4
Re: Big O notation confusion
Posted 24 June 2010  11:41 PM
We aren't exactly choosing to bound it with an exponential function it simply is bounded by an exponential function, as this function is the parent graph of quadratics, cubics, n^1.5, etc. And as n^2 > n^1.5, we can't say that n^2 bounds n^1.5. Also, if you graph nlog(n) vs. n^1.5, you'll notice a huge difference in curveature. That is because a linearithmic graph is not quite exponential in nature.
Really, you might want to ask someone with a stronger number theory or computer science background than myself some of these questions. But I do hope I cleared up some of this.
#5
Re: Big O notation confusion
Posted 25 June 2010  12:02 AM
macosxnerd101, on 24 June 2010  10:41 PM, said:
I think that is my point of confusion right there. We must be using a different definition of the term "bounding." In my mathematical vocabulary it is proper to say that a function is "bounded" above, if, for every input value, the output value of the bounding function is greater than the output value of the bounded function. It's the definition that both the squeeze theorem and limit comparison test are both based upon.
I do greatly appreciate the help you're giving though, but I may have to end up taking your advice on asking someone with a better numbertheoretic background.
#6
Re: Big O notation confusion
Posted 25 June 2010  06:33 AM
You can see how this result is derived here in the link. It basically comes down to evaluting the given sum, and approximating with an integral. You derived that the algorithm was O(n^1.3) ish, which is technicaly correct, but not as tight as it can be. Your O(n^1.3) = O(n * n^0.3) and we know that n^0.3 > loglogn  So, your calculations weren't wrong, but just not as tight as it could be.
The reason the seive is an exponential algorithm is because this is expressed in terms of bit operations, (there are log(n) bits used to represent n), and making that substitution, you would see that the algorithm is exponential ... (I THINK  so correct me if I'm wrong)  You can read this here http://livetoad.org/.../lecture_01.pdf
"This tells us that the sieve is fairly inefficient. Why? The size of the input is on the order of log(N), since up to constant multiple that is the number of digits of N. For example, if we work in binary then the number of bits needed to express N is roughly log2(N) = log(N)/ log(2). However the running time is exponential in log(N)" (Quoted from the second link)
I'm not an expert in number theory either, but I hope this helps.
Zach
This post has been edited by Nizbel99: 25 June 2010  06:36 AM
#7
Re: Big O notation confusion
Posted 25 June 2010  11:14 AM
Nizbel99, on 25 June 2010  05:33 AM, said:
I'm sorry, the n^1.3 actually referred to a calculation I made on a different algorithm of my own creation that is similar to the Sieve of Eratosthenes; mine runs more slowly, but uses only a fraction of the memory. I just posted the value here because I thought my algorithm was similar enough to the Sieve that the value would be at least partially relevant.
The derivation in your link was extremely helpful, and it should allow me to derive the exact runtime of my own algorithm. Thanks a lot!
#8
Re: Big O notation confusion
Posted 12 May 2013  08:28 PM
starving_mathematician, on 24 June 2010  10:56 PM, said:
Hello, I realize this post is really old, but I'd still like to clarify a few things for those that might happen by.
First of all, what does it mean for a function to be exponential. Wikipedia considers things of the form 2^poly(x) to be exponential. Either way, in exponential functions, x is in the exponent. Personally, I consider things like 2^x or 3^x to be exponential. I'll be using 2^x in this post.
Second of all, what does it mean for a function f(x) to be O(g(x)) (BigO notation). Informally, it means that g(x) can act as an upper bound for f(x) as x approaches infinity. Let's say the sieve of eratosthenes takes exactly f(x) operations to run. You say f(x) is not even quadratic. For sake of argument, let's suppose f(x) = x^2. Let g(x) = 2^x. f(x) < g(x), for x > 0. Therefore, g(x) is an upper bound for f(x). This means that f(x) is O(g(x)). f(x) is also O(x^3), O(x^4), O(x^x) and O(x!). All of these can act as upper bounds to f(x). f(x) is not O(1) since it doesn't take constant time to run.
Last of all, I recommend looking up BigOmega notation and BigTheta notations and comparing them with BigO notation. BigOmega is the lower bound equivalent of BigO. Using f(x) = x^2, f(x) is BigOmega(1) and BigOmega(x) since both are possible lower bounds for x^2. BigTheta describes the exact timecomplexity of the algorithm. In other words, if f(x) is BigTheta(x^2) we know that f(x) is exactly quadratic. f(x) might be 2*x^2 or .5*x^2. Both would be considered exactly quadratic in my book. Notice that out of all the three, BigTheta notation is actually the most powerful and informative. BigO notation is used more often because it's easier to establish an upper bound and because it still provides a worst case scenario on what we could expect. BigOmega isn't used very often because it's a lower bound. It tells how fast we ever can hope to make the algorithm but no bound on how much time it could actually take.
In summary, the sieve is O(2^x) even though that doesn't mean much because it's also O(x^3), O(x!) and much, much more.
