# Prime Complexity

Computer Science Level 3

What is the runtime of the following pseudocode?

 1 2 3 4 5 6 7 8 9 function(n) array x of n+1 booleans, all set to true x[0] = x[1] = false for i in 2 : n if x[i] = true j = 2 * i while j < n x[j] = false j += i 

Details and Assumptions:

• The question asks for the best upper bound to the runtime of the pseudocode, so if you think there are multiple correct answers, choose the answer which is the best upper bound among them.
×