Big O Time Complexity for a for loop when the number of iterations isn't constant, but the range of number of iterations is known

As I'm aware, if you have a for loop which has a constant value for the number of iterations, such as 1000, then the time complexity should be O(1). But if the number of iterations is unknown, and is instead left to the user's input, and the input can be specified as any number, then it is O(N).

However, what if the number of iterations is unknown, but you know the range of the number of iterations? Let's say, the range would be somewhere between 10-28 iterations 100% of the time. Would the time complexity be O(1) or O(N) and why?

The time complexity would still be considered O(1). The number of iterations is always bounded by a fixed constant, and does not depend on the input size. Also important is, that time-complexity is determined by the worst case scenario, which in your case would be 28 iterations, a fixed size.

The problem you're into is something that a lot of tutorials and explanations about big-O notation get wrong.

O(n) isn't magical. That n means something specific. In the vast majority of cases, nobody tells you what the n is referring to. For example, someone tells you:

"Quicksort is O(n log n)" - they are talking gobbledygook - that statement doesn't mean anything at all. Here's the correct statement:

"For a given list of n elements, and given an oracle that can determine for any 2 such elements which one is earlier is constant time, sorting that list with the quicksort algorithm is has O(n log n) performance".

One crucial difference is that n HAS TO BE DEFINED for the statement to make any sort of sense. Now, that's a mouth full, and it's kinda obvious that the n in "Quick sort is O(n)" is referring to the size of the list. It's even, effectively, obvious that the performance of the comparison function is disregarded. After all, even if that is O(q) (whatever q might be - remember, O(n) on its own is a completely meaningless statement, that n has to be defined) - then the performance of sorting it is O(q*n log n) - point is, the contribution to the performance purely from the sort algorithm is the n log n bit. So, before you barrage someone with vitriol for simplifying it all down to "Quicksort is O(n log n)" keep in mind it's a sensible simplification.

So what does O(n log n) even mean?

It simply means this:

Make a graph with n on the X-axis (whatever it is), and the total time the algorithm would take the perform the job (whatever that is) on the Y axis, and you draw that curve out, eventually, for a large enough n where we have no way of knowing what that is, the graph looks identical to the graph you get when graphing y = x * log x.

So, what does that mean in light of your question? nothing - remember, n is whatever you say it is. It is disingenuous to paper over constant factors. The computer and the programming language spec do not mention any of this stuff, the only point of talking about performance characteristics is for one human coder or designer talking to another to convey certain ideas.

Here is an example: A java ArrayList is hard-bounded: It cannot possibly contain more than 2^31-1 elements. This is specced behaviour (the index value is defined by the API to be an int, which means having more elements means e.g. list.size() cannot possibly give the right answer, as the right answer doesn't fit an int)!

So, can we say that quicksorting an arraylist is therefore O(1), because, after all, the amount of elements it could possibly contain is hard-bounded and therefore can be disregarded?

You could. Let's say you are perfectly aware of that. Your brain has formed this thought and wants to convey it to another person. So, your brain thinks about it, makes your mouth move and your lungs expel air, and out of your mouth flows:

"ArrayList sorting behaviour is O(1)"

That moving air enters my eardrums, turns into nerve pulses and enters my brain. There are now only two options and which one happens depends on the people who own the mouth and the ears:

• The person who hears it is on the same page and understands the full impact of that statement, and understands that this is about the fact that arraylist is hard bounded.
• The person who hears it does not understand that little detail.

If the second thing happens, then communication failed. You might as well have been speaking northeast Plutonian.

"Algorithm X is O(1)" is already teetering on the edge of so oversimplified as to be useless (you didn't bother to explain vs. which variables). If you say that when:

• you did not define any variables, you're just assuming the person who reads your text or hears your words intuits which variables you are talking about.
• You also aren't mentioning anything at all about the relevant bounds.

If you were communicating like that in my dev team, or a student pulls that stunt, I'd fail them. We can hold a 5 hour debate on what 'algorithm Y is O(1) means' but at some point it's like a debate on what "literally" means - in the end things mean what most people think they mean.