Big O time complexity for limited input

user_19245296 0
Viewed 62

I am new to Big O time complexity...

if I have a function that is calculating if a number is prime or not, but I am told that I can be guaranteed that the input parameter, p, will ALWAYS be less than 100, does that mean that the overall Big O time complexity is constant as O(1)?

Meaning, even if the worst case is that it will have to check every number up until p//2, at the worst case, p is 100 and this will mean that it will run 100 // 2 times and that is constant O(1)?

I hope that makes sense!

python
2 Answers

No, it is not O(1).

Short answer: if p changes, the function takes longer to run. O(1) would mean that regardless of the value of p, the runtime would not change.

The purpose of O(n) is to describe the behavior of the the function for varying input, so it will give you an understanding of how much slower it will run if you for example, double n.

In fact, there are superior algorithms to calculating if a number is prime, and the amount of time each takes to run will scale differently. As a result, it is important to correctly classify the complexity of what you have now in order to evaluate what is better.

user_116598810

This is a valid perspective, but unlikely to be the answer that your homework is looking for. You might get a bonus mark if you can frame it correctly but you should still answer the "real" question.

When I look up the definition of Big O, I see

... a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

We normally think of this as "tends toward infinity", in which case you could say that this is O(1), i.e. the run time is constant as you tend toward infinity (above 100,000). But if we use "a particular value" (being 100,000) then no, this is not O(1).

To determine Big O would should consider the relationship between the input value N and the number of inner loop iterations, up to & before the maximum value of 100,000. If you double N, what's the impact on number of inner loop iterations?

user_1460770
Related