Runtime – Modulo Operator Runtime

runtime

I am reading a review sheet for a class and the instructor said this of the modulo operator:

Remember that modulus (%) has a runtime of O((logn)^2).

He continued to display this piece of code:

//Assumes n > 1

public boolean isPrime2 (int n) {
    int sqrtN = (int) Math. sqrt (n) ;
    for(int i = 2; i < sqrtN + 1; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

He said of this code:

O(n) = sqrt(n) x n^2. As you can see, this method of checking if a number is prime only iterates from 2 to sqrt(n). Since we loop over a quadratic operation sqrt(n) times, the runtime is O(sqrt(n)).

Two things I don't understand. One, why is the inside the for loop now an n^2 operation rather than a (logn)^2 operation. Two, even if it is only an n^2 operation, shouldn't the total runtime then be O(n)?

Best Answer

I assume the review sheet you are reading is flawed:

  • Modulo/remainder is a O(1) operation (it's essentially just a variation on division, which takes constant time on fixed-sized numbers).
  • Therefore, the inside of the loop is an O(1) operation,
  • which makes the total complexity O(√n).

However, let's assume for a moment that % would denote a waste-time-operator with complexity O(log(n)²). In that case, we would end up with a complexity O(√n · log(n)²). The expression √n · log(n)² cannot be simplified. However, the complexity class O(√n · n²) includes O(√n · log(n)²):

   O(√n · n²) includes O(√n · log(n)²)
⇔    √n · n²      >      √n · log(n)²
⇔         n²      >           log(n)²   assuming n ≠ 0
⇔         n       >           log(n)    assuming n > 0
which is true for n > 1

Of the three conditions n ≠ 0, n > 0, n > 1 the last one is the strongest, and is guaranteed by a comment in the code. It would therefore be correct to say that the code has O(√n · n²) complexity, although it is also true that it has O(√n · log(n)²) complexity, which is a stronger statement.

Note that the expression √n · n² can be simplified, but not to n:

   √n · n²
=  n1/2 · n²
=  n1/2 + 2
=  n5/2
=  √(n5)
Related Topic