-4

I have a pseudo code from university:

(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[]

Now I have to calculate the Big O for this pseudo code.

We learnt to make it step by step, by adding up the number of operations.

This is what I got so far:

Comparisons:

(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

Assignments:

(1): 1
(6): (n - 1)

(1) + (6): n operations for all assignments

Division:

(4): (n-1)(n-2) outer loop * inner loop

n^2 - 3 n + 2 operations for the division.

So if you add up those numbers:

(n^2 - 2 n + 1) + n + n^2 - 3 n + 2 = 2n^2 - 4 n + 3

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.

Can you guys please help me figuring out, what my misconception is. Thanks

HelplessStudent
  • 9
  • 1
  • http://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation Here's an explanation of big O. O(2n^2) isn't a tight big O bound, to say the least. – fileyfood500 May 18 '17 at 23:02
  • This algorithm is so close to the Sieve of Eratosthenes, I don't understand why you don't add the one extra line that would [considerably improve the time complexity](http://stackoverflow.com/q/2582732/1553090). – paddy May 18 '17 at 23:02
  • @paddy That may be where the instructor is headed. – pjs May 18 '17 at 23:03
  • This is the pseudo code, I have to work with. – HelplessStudent May 18 '17 at 23:04

3 Answers3

1

Your misconception is thinking that 2n^2 is not O(n^2). Big-O ignores scaling constants, so you can ignore the 2 out front.

pjs
  • 18,696
  • 4
  • 27
  • 56
  • Okay, thanks for that insight. Now I only need to know, whether the calculation of the number of operations is right, so that I can continue on another algorithm. – HelplessStudent May 18 '17 at 23:03
1

Calculation of the inner loop is wrong:

When the outer loop (i) goes from 2 to n then the innerloop wil iterate no more then 0 + 1 + 2 + ... + n-2 times, which equals to the sum of the first n-2 natural numbers.

The formula for the sum of the first n natural numbers is n*(n+1)/2.

Since there is a -2 offset the maximum number of iterations of the innerloop would be (n-2) * (n-1) / 2.

user7994388
  • 448
  • 3
  • 6
0

Actually you've already got the correct answer!

Thats because O(2*n²) equals O(n²). Constants multiplicators don't affect Big-O. For more information on the math behind it I recommend reading about Asymptotic Analisys. To keep it simple, it has to do with when the n tends to infinity.

Gustavo Sutter
  • 94
  • 1
  • 7