Prime Complexity

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.
×

Problem Loading...

Note Loading...

Set Loading...