Modulo Operator 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)?

• Sounds like the instructor is talking through his hat. I can't see how the modulo operator could be dependent on anything other than the number of bits in its arguments. – Emmet Jul 25 '14 at 7:50
• Well, I have a few friends currently taking a Discrete Math and Probability course in which they also mentioned that the modulo operator takes O((logn)^2) time. – rakrakrakrak Jul 25 '14 at 7:54
• What is `n` in this case? If it's not the bit-length of the operands, I can't see how it's in any way related. If it is, then it's well-known that long division is O(n) and I can't see how modulo could be worse. – Emmet Jul 25 '14 at 8:00

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)
```
• That little word fix-sized is important, because it allows us to drastically simplify complexity investigations: Any operation with `O(f(x))` is equivalent to `O(1)` iff `x` is a constant, regardless of what `f` is. So it doesn't matter if modulo takes `log(n)²` for arbitrary-precision numbers, if we're only over going to use 64-bit integers. – amon Jul 25 '14 at 8:20
• In p mod q where p is m bits long, it may be the case that the complexity modulo is O((lg m)^2), and that the confusion is being caused by m (bitlength) and n (loop bound) being conflated. – Emmet Jul 25 '14 at 8:21