title: Calculating time complexity for finding first 'n' prime numbers
body: <p>The algorithm for finding first 'n' prime numbers is:</p>
  
  <pre><code>while (number &lt;= n) {
    boolean isPrime = true; 
    for (int divisor = 2; divisor &lt;= (int)(Math.sqrt(number)); divisor++) {
      if (number % divisor == 0) {
        isPrime = false;      
        break;
      }
    }
    if(isPrime) 
      System.out.print(number + " ");
  }
  </code></pre>
  
  <p>The book, "Introduction to java programming", calculates big-O for this algorithm as:</p>
  
  <p>Since it takes √i steps in the <code>for</code> loop to check whether number i is prime, the algorithm takes √2 + √3 + √4 + ... + √n steps to find all the prime numbers less than or equal to n.</p>
  
  <p>Observe that,</p>
  
  <p>√2 + √3 + √4 + ... + √n &lt;= n√n</p>
  
  <p>Therefore, the time complexity for this algorithm is O(n√n).</p>
  
  <p><strong>Que:</strong></p>
  
  <p><strong>1.</strong> He says, "it takes √i steps in the <code>for</code> loop to check whether number i is prime".</p>
  
  <p>Don't you think it should be (√i-1) steps.</p>
  
  <p><strong>2.</strong> Please explain how</p>
  
  <p>√2 + √3 + √4 + ... + √n &lt;= n√n </p>
  
  <p>(I know the relationship holds if you just replace 'n' with a random number. I need explanation)</p>