Big O for an algorithm for finding prime numbers : <p>I have a pseudo code from university:</p>

<pre><code>(0) initialize logic array prim[ n ]
(1) prim[ 1 ] = false
(2) for i = 2 to n do
(3)   for k = 2 to i − 1 do
(4)     if i % k == 0 then
(5)       break
(6)     prim[i] = (k == i) // Was loop (3) fully executed?
(7) return prim[]
</code></pre>

<p>Now I have to calculate the Big O for this pseudo code.</p>

<p>We learnt to make it step by step, by adding up the number of operations.</p>

<p>This is what I got so far:</p>

<p>Comparisons:</p>

<pre><code>(4): (n-1)(n-2) outer loop * inner loop
(6): (n-1) outer loop

(4) + (6): n^2 - 2 n + 1 operations for all comparisons
</code></pre>

<p>Assignments:</p>

<pre><code>(1): 1
(6): (n - 1)

(1) + (6): n operations for all assignments
</code></pre>

<p>Division:</p>

<pre><code>(4): (n-1)(n-2) outer loop * inner loop

n^2 - 3 n + 2 operations for the division.
</code></pre>

<p>So if you add up those numbers:</p>

<pre><code>(n^2 - 2 n + 1) + n + n^2 - 3 n + 2 = 2n^2 - 4 n + 3
</code></pre>

<p>I think there is somewhere a misconception from my side, because the Big O should be O(n^2) but here it is O(2n^2) from what I understand.</p>

<p>Can you guys please help me figuring out, what my misconception is. Thanks</p>
