finding the running time for my algorithm for finding whether an input is prime in terms of the input

Question

This is my function for finding prime numbers

void print(int num)
{
    for(int i=2; i<num/2; i++)
    {
        if(num%i==0)
        {
            cout<<"not prime\n";
            exit(0);
        }
    }
    cout<<"prime\n";        
}

My input in num. I'm trying to find the runtime using big oh. I remember that finding the run time had something to do with log.

The worst case would be that my program would run the n/2 -1 times?

Answer 1

Yes, the loop runs n/2-1 times and only contains commands of constant complexity, so your runtime scales as a*(n/2-1) for some a. In big-o this is written as O(n/2-1) and because constant factors don't matter this is equal to O(n).

(as an aside: it is actually theta(n) which means, that it is not just bounded from above by n but also from below by n)