You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)! :)
O(n) is meaningless if we don't say anything about "n", so no, 'iterating an array" is not necessarily O(n) - it's only so when the array has a size proportional with the input.
Or, to put it differently: yes "array.includes" is not O(1) in common discussions, because typically we discuss the complexity of method `includes` as relative to the size of the array; but a program/algorithm that contains an invocation of `array.includes` does not automatically have complexity that is linear or worse - it can very well be logarithmic or constant. For example, looking up a value in a hashtable where the keys are strings is considered to be constant time, even though you need to iterate over the key in order to obtain its hashcode (i.e. the algorithm that takes a string and produces a hashcode is O(n) where n is the length of the string).
And as to your second point, the choice of what is and isn't a constant-time operation is generally a practical concession. There's no reason to say "you can't say anything about any algorithm because it's an implementation detail" here. The conversation is specifically about element presence in an unsorted array. A very simple, easily understood, and unambiguous algorithm. Bringing up the runtime of the operation in a hashtable or in tree-structures is entirely nonsensical and just destroys any conversation there is to be had.
The only way I can see it making sense is because a function could take arbitrarily many arguments. Why on earth would that matter if the function doesn't do anything with those arbitrarily many arguments? We may not know in advance what a caller gives to a function, but of course we know what the function does with its arguments--it's a function's body that we're analyzing and classifying a Big-O for!
In general, it is O(N). In this example, it is O(1). When your N is fixed (or even upper bounded), then it is always O(1). This is standard in how it is taught, and I've even said O(1) in interviews where I had a nested for loop, because the size of the iteration was fixed in both loops. The interviewer agreed with me.
Heck, I did this even in an interview where N could be arbitrarily large, but I argued that for the problem domain, it is extremely unlikely that N would be bigger than some amount - here N represented the number of direct reports a manager has. I said that in theory it was O(N), but in practice (or on average), it would be O(1). Again, the interviewer accepted the answer.
I had to read this sentence over several times. I... think you've just filled in a missing piece of my college CompSci education.
Previously, I never really understand why we measured algorithms this way, beyond "it's a rough classification and nothing is perfect." What I didn't quite realize until just now is, this classification assumes N is a variable that could be any value in the universe—and so you have to optimize for that eventuality.
If N is known, the iterations don't matter—because of course they don't.
(Disclaimer: I've been out of college for a while and I don't use algorithms in my daily life, it's possible I just forgot this. Or that I'm making a fool of myself right now!)
isVowel(c) implemented using array.includes() on a fixed size array is O(1) operation - it does not depend on the size of its input.
You can see this more clearly by asking what complexity does array.all(isVowel) have? Well, for each character in array, it needs to do 5 comparisons. So, for n characters it will do 5 * n operations. So, it is in O(n). This also proves that isVowel() is an O(1) operation.
Now, if we were to think about comparing to all vowels in all languages, you can also say that isVowel() is O(n) complexity in the number of vowels. The above analysis would show that array.all(isVowel) is O(n * m), with n being the number of characters in array and m being the number of vowels we are considering. Even this though is pretty strange, since Big O complexity analysis is only relevant if you are interested in the growth of n and m, which is unlikely for the number of vowels.
> At best you could say it is O(n)*O(1) which is formally equivalent to O(n).
Sorry, that's not how you would use or define multi-variable Big-O notation, if you want it to make any sense.
See eg https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variab... for more details.
Yes, but the parent wrote O(n, 1) not O(n * 1). Does O(k, log n) exists?
> Sorry, that's not how you would use or define multi-variable Big-O notation, if you want it to make any sense.
What do you mean? If I have f: n -> n and g: n -> 1, can I not say O(f) * O(g) = O(f*g) ? See https://math.stackexchange.com/a/2317054 for an example of demonstration.
Big-O is a mapping from a function, like O(n -> 1) or (n -> n) or (n -> n^2) or (x -> sin x) to a set of functions.
Function don't care about renaming of arguments. (n -> 2 n) is the same function as (x -> 2 x).
When you write O(k log n) what you really mean is O((k, n) -> k log n)
And you can indeed take it apart:
O((k, n) -> k) * O((k, n) -> log n) == O((k, n) -> n log n)
(For some suitable definition of what multiplication of sets of functions means.)
That's very different from functions with single arguments like in your example.
(And, yes, your example works. It's just a different thing.)