Am I Right In My Calculation of the Worst Case of This Code?

60 Views Asked by At
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!