4 ms·
Yes, isVowel regardless of its implementation has all its input of fixed size, both the array and the one element to look for. In that case, wouldn't any imple
by Znafon 6y ago
Yes, isVowel regardless of its implementation has all its input of fixed size, both the array and the one element to look for.
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 .
- saagarjha 6y ago> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever? 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) is still O(1), it just has a higher constant factor. The only exception is that you could have psuedo-polynomial algorithms that depend on the value input itself, like func foo(i: Int) { for _ in 1...i { print(i) } }
- formerly_proven 6y ago> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever? Yes.