Hacker News new | ask | show | jobs
by redactyl 2090 days ago
A linear time algorithm ('.includes') is a constant time algorithm when its input is constant. Of course, the other input to '.includes' (the char) can vary in value, but to know if that affects running time we'd have to look at the implementation of '.includes'.
1 comments
adamzerner 2090 days ago
I'm not sure what you mean, how can it be constant? You have to check each element in the array and there are n elements in the array.
link
3np 2090 days ago
If you define `n` as "the number of vowels in the input language", making it dynamic, then yes.

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 ;)

link
adamzerner 2090 days ago
Yeah, I have learned a few things from the comments here and my understanding isn't perfect. Previously I thought of `n` as arbitrary; that it can be whatever you define it to be. I see now that you're right that technically it has a more precise definition: it refers to the input size.

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.

link