Algorithms and Data Structures · Junior · Question 64 of 75
What is the time complexity of the isPrime check below?
function isPrime(n) {
if (n < 2) return false;
for (let i = 2; i * i <= n; i++) {
if (n % i === 0) return false;
}
return true;
}- 1O(n)
- 2O(log n)
- ✓Correct answer: O(√n)
Explanation
The loop stops when i * i > n, so it runs at most √n times. A divisor larger than √n would pair with one smaller than √n, which the loop has already checked.