7 Replies - 6365 Views - Last Post: 12 May 2013 - 08:28 PM

#1 starving_mathematician  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 24-June 10

Big O notation confusion

Posted 24 June 2010 - 10:56 PM

If my question seems idiotic, it's because everything I know about Big O notation comes from skimming the wikipedia page on it, but here it goes anyway: why is an algorithm like the Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) considered to be exponential?

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 prime-counting 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?

Is This A Good Question/Topic? 0
  • +

Replies To: Big O notation confusion

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10551
  • View blog
  • Posts: 39,053
  • Joined: 27-December 08

Re: Big O notation confusion

Posted 24 June 2010 - 11:04 PM

It is actually O(n^1.5), as the outer loop goes from 2-sqrt(n), and the inner loop goes for n iterations. So sqrt(n) * n (nested loops, multiply) --> O(n * sqrt(n)), or O(n^1.5). For the purposes of Big-O, we drop the coefficient pi in the pi * sqrt(n) term. As the exponent is greater than 1, it is bounded by an exponential function.
Was This Post Helpful? 1
  • +
  • -

#3 starving_mathematician  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 24-June 10

Re: Big O notation confusion

Posted 24 June 2010 - 11:16 PM

View Postmacosxnerd101, on 24 June 2010 - 10:04 PM, said:

It is actually O(n^1.5), as the outer loop goes from 2-sqrt(n), and the inner loop goes for n iterations. So sqrt(n) * n (nested loops, multiply) --> O(n * sqrt(n)), or O(n^1.5). For the purposes of Big-O, we drop the coefficient pi in the pi * sqrt(n) term. As the exponent is greater than 1, it is bounded by an exponential function.


I guess I didn't make this part clear. The "pi" I wrote is not the constant 3.14159... It represents the prime-counting 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

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10551
  • View blog
  • Posts: 39,053
  • Joined: 27-December 08

Re: Big O notation confusion

Posted 24 June 2010 - 11:41 PM

As the Sieve of Eratosthenes is a method of implementing pi(x), then we can't use it in the Big-O definition (at least, not without causing infinite recursion ;)).

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. :)
Was This Post Helpful? 0
  • +
  • -

#5 starving_mathematician  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 24-June 10

Re: Big O notation confusion

Posted 25 June 2010 - 12:02 AM

View Postmacosxnerd101, on 24 June 2010 - 10:41 PM, said:

And as n^2 > n^1.5, we can't say that n^2 bounds n^1.5.


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 number-theoretic background. ;)
Was This Post Helpful? 0
  • +
  • -

#6 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Re: Big O notation confusion

Posted 25 June 2010 - 06:33 AM

I've done a bit of research and seem to keep finding that this algorithm has a run time of Theta(nloglogn) http://www.cs.hmc.ed...s/Sieve-JFP.pdf

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

Was This Post Helpful? 1
  • +
  • -

#7 starving_mathematician  Icon User is offline

  • New D.I.C Head
  • member icon

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 24-June 10

Re: Big O notation confusion

Posted 25 June 2010 - 11:14 AM

View PostNizbel99, on 25 June 2010 - 05:33 AM, said:

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.


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 run-time of my own algorithm. Thanks a lot!
Was This Post Helpful? 0
  • +
  • -

#8 courageousmonkey  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 12-May 13

Re: Big O notation confusion

Posted 12 May 2013 - 08:28 PM

View Poststarving_mathematician, on 24 June 2010 - 10:56 PM, said:

why is an algorithm like the Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) considered to be exponential?


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)) (Big-O 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 Big-Omega notation and Big-Theta notations and comparing them with Big-O notation. Big-Omega is the lower bound equivalent of Big-O. Using f(x) = x^2, f(x) is Big-Omega(1) and Big-Omega(x) since both are possible lower bounds for x^2. Big-Theta describes the exact time-complexity of the algorithm. In other words, if f(x) is Big-Theta(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, Big-Theta notation is actually the most powerful and informative. Big-O 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. Big-Omega 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1