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:
O(1)
operation (it's essentially just a variation on division, which takes constant time on fixed-sized numbers).O(1)
operation,O(√n)
.However, let's assume for a moment that
%
would denote a waste-time-operator with complexityO(log(n)²)
. In that case, we would end up with a complexityO(√n · log(n)²)
. The expression√n · log(n)²
cannot be simplified. However, the complexity classO(√n · n²)
includesO(√n · log(n)²)
: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 hasO(√n · n²)
complexity, although it is also true that it hasO(√n · log(n)²)
complexity, which is a stronger statement.Note that the expression
√n · n²
can be simplified, but not ton
: