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)?
3
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)
2