title: How to solve Big-O Notation for prime number function?
body: <p>I am trying to understand Big-O Notation. So sorry if I am asking something that is too obvious but I can't seem to wrap my head around this.</p>
  
  <p>I have the following C# code function that I am trying to calculate Big-O Notation for.</p>
  
  <pre><code>for (i = 2; i &lt; 100; i++)
       {
          for (j = 2; j &lt;= (i / j); j++)
             if ((i % j) == 0) break; // if factor found, not prime
          if (j &gt; (i / j)) 
             Console.WriteLine("{0} is prime", i);
       }
  </code></pre>
  
  <p>Now what I got so far is that I think that both the <code>if</code> clauses are considered constant O(1) and not taken into account for the calculation of this algorithm? And also if I have understood correctly a single for loop</p>
  
  <pre><code>for(i = 0; i &lt; 100; i++)
  </code></pre>
  
  <p>since it is a linear function would be O(n) and a nested loop that does not depend on a variable from the surrounding loop </p>
  
  <pre><code>for(i = 0; i &lt; 100; i++)
      for(j = 0; j &lt; 100; j++)
  </code></pre>
  
  <p>Is O(n^2)? But how do I calculate a function such as the top one where the second loop is dependent on the first loop and creates a non-linear function? </p>
  
  <p><img src="https://i.stack.imgur.com/cPVZ6.png" alt="Picture of my data points"></p>
  
  <p>I found a definition for linearithmic that says</p>
  
  <blockquote>
    <p>Linearithmic algorithm scales to huge problems. Whenever N doubles,
    the running time more (but not much more) than doubles.</p>
  </blockquote>
  
  <p>While this seems to be a good description of how this code snippet runs would that mean that it is O(N Log[n]) and if so how could I calculate this?</p>