Re:Big O, Little N
by tsimionescu on Friday October 02, 2020 @08:21AM
(#24661857)
array.includes() is an O(n) method in the size of the array.
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.
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.