title: Time complexity of Sieve of Eratosthenes algorithm
body: <p>From <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="noreferrer">Wikipedia:</a></p>
  
  <blockquote>
    <p>The complexity of the algorithm is
    <code>O(n(logn)(loglogn))</code> bit operations.                  </p>
  </blockquote>
  
  <p><strong>How do you arrive at that?</strong></p>
  
  <p>That the complexity includes the <code>loglogn</code> term tells me that there is a <code>sqrt(n)</code> somewhere.</p>
  
  <hr>
  
  <p>Suppose I am running the sieve on the first 100 numbers (<code>n = 100</code>), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use <code>mark_composite()</code> would be something like </p>
  
  <pre><code>n/2 + n/3 + n/5 + n/7 + ... + n/97        =      O(n^2)                         
  </code></pre>
  
  <p>And to find the next prime number (for example to jump to <code>7</code> after crossing out all the numbers that are multiples of <code>5</code>), the number of operations would be <code>O(n)</code>.</p>
  
  <p>So, the complexity would be <code>O(n^3)</code>. <strong>Do you agree?</strong></p>