Hunter McMillen wrote:Just because you don't iterate from 0 to N doesn't mean that you don't operate on every element from 0 to N.
But, as Ulf pointed out, that's not the major reason that an algorithm is O(n).
The O notation is used mainly as a guide to
behaviour; specifically, as to how it's likely to change with changes in the amount of input. It should also be pointed out that it is
not necessarily a good guide as to how long something will run, because 'O' is generally not defined.
Most often, the only things you're interested in are whether it's O(n), O(log n) or O(1).
I know this because I got it wrong...a while ago, it has to be said.
Also, this thread is 3 years old; you probably shouldn't post on it.
Now
that is a good point; which I've unfortunately just broken myself.
Winston