Compute Big-O for a program in Java

I just would like to ask that what is Big-O for this program. I think It's n/2, but I am not sure.

public static boolean isPrime(int k) {
    if (k <= 1)
        return false;
    else if (k > 2 && k%2 == 0)
        return false;
    else 
    {
        for(int i = 3;i<=k/2;i+=2)
            if (k % i == 0)
                return false;
    }
    return true;
}

1 answer

  • answered 2018-04-14 14:35 Zabuza

    The complexity is O(k) which is linear time.

    Take the worst case execution where k is a prime. Then your algorithm will execute all lines until the return true;.

    Particularly you completely execute the for loop which yields (k / 4) - 3 iterations:

    for (int i = 3; i <= k/2; i += 2)
    

    So you get O((k / 4) - 3) which is O(k).