0

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?

Improve this question
1
  • 1
    I don't know if it matters, but this code is very inefficient. Commented Feb 24, 2014 at 0:51

1 Answer 1

Reset to default
3

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)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

@TonyD too bad I mixed up little o and theta :-( it is actually theta(n) and not o(n). I will change it to O(n) because it is much better known than theta...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.