bool isPrime(int n) {
bool bVal = false;
if(n<=1){
return bVal;
}
for (int k= 2; k<n; k++) {
if (n%k==0) {
return bVal;
}
}
bVal = true;
return bVal;
}
The input is said to have a range from $0 \leq n \leq 10\ 000\ 000$. I believe that the worst case will occur for the closest prime to $10\ 000\ 000$ (i.e. the largest within the bounds), whatever that may be, since the loop will check all the numbers up to but not including $n$ for a complexity of $O(n)$, realize it is not prime, and then exit the loop to make one final assignment before returning bVal. This would give a final worst case complexity of $O(n)$.
Is this more or less correct, or have a made an error?
Any help would be greatly appreciated!