However, I think the example still demonstrates the larger point that I was making. `.includes` takes linear time proportional to the array that calls it, but the fact that it's linear time isn't a bad thing because the size of the array is five.
However, the list of vowels in the function is static. So the execution time doe snot grow as the input size grows (there is only a single char as input).
O(5) = O(1) = constant.
.includes() is O(n), though.
Sounds like you might need a refresher (it's easy to get fuzzy over the years, happens to the best of us).
But you may want to update the blog post as not to confuse others more, I think people have exams coming up ;)
However, I also think that in _practice_, as Znafon [says](https://news.ycombinator.com/item?id=24661411), the meaning of `n` is clear and it makes sense to stretch the technical definition a bit. In my experience, people often do. Imagine if there were one trillion vowels. It wouldn't be practical to describe it as an O(1) algorithm, despite what the answers to exam questions might say.
That said, I think that it is worth understanding the distinction between what `n` means in theory vs practice, so I was going to add a note to the blog post in order to avoid confusing readers, like you recommend. However, as I tried to do so, things got too side-tracked. Too many tangents, especially ones that aren't the easiest to understand, makes the post harder to follow. So I decided on linking to this thread parenthetically. That seems to my eye to strike the right balance.
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.)
Any function taking just a char would be O(1) since it only has 256 values n can take, discussing their complexity would be meaningless making it obvious that someone talking about the complexity of includes() is talking about the size of the array.
The goal of computer science is to get insight about the performance of programs, not being pedantic and reduce the problem to the absurd that have an obvious answer, in this context the meaning of O(n) is perfectly clear.
Remember that O() is concerned with asymptotic behaviour as the input grows - for a constant set of vowels to check against, the running time does not grow and the function is therefore O(1).
An O(n) function can absolutely be part of an O(1) function.
To the authors point, Big-O describes asymptotic growth and for small values of n, O(n^2) may perform better than an O(1) function. You also need a definition for `n`. What would you define as `n` for the `isVowel` function?
In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?
Maybe we should only talk about properly defined algorithms whose inputs have been formally defined, but since we are talking complexity, I assumed something will grow.
It is either the array, or `char`. The set of vowels is finished for a given language but its size can change between languages and `char` will always be less than 256 (or some other fixed value).
Since isVowel is a closure it's not crazy to consider the array as part of the input.
You say "the only useful interpretation would be to consider this function O(1)" but it is possible to read this as an example and that n relates to the size of the array and in that case saying it is O(n) makes sense.
Since this is not a formal discussion of complexity and n has not been defined, I think it's fairer to interpret the post in a way where it makes sense .
Yes, because there is no "n" involved. For example, this code:
for i in 1...1_000_000 {
print(i)
}
return ["a", "e", "i", "o", "u"].contains(character)
func foo(i: Int) {
for _ in 1...i {
print(i)
}
}Yes.
All that aside, I agree that the OP is O(1). It does 5 comparisons. It always does 5 comparisons, regardless of the input of the isVowel function. Yes, includes, evaluated out of context, is O(n), but you know something about the context it's used in to be able to give isVowel a tighter bound. That's usually what the goal of Big O is; not to define ~a~ bound, but define the most conservative.
> [... ] it hit me that it's actually O(n), because we've got an array and have to iterate over every element to see if the element matches char.
This depends on how you define your `n`. Usually this would be defined as the input size. Unless you would like to be able to run this on arbitrary definitions of what a "vowel" is (and in this case, it's indeed both small and static), the only useful interpretation would be to consider this function O(1), regardless of iteration over this 5-element list. If the list of vowels would considered a parameter, it would indeed be O(n) or O(m).