Hacker News Reader

Comment by 3np | Hacker News Reader

> const isVowel = (char) => ["a", "e", "i", "o", "u"].includes(char);

> [... ] 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).

View on HN

Author here. Yeah that makes sense. I didn't realize it at the time.

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.

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'.

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.

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

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.

Yep O(5) = O(1)

You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)! :)

Depends. Are we talking about people who know what O(n) means? Parent comment explained it very well - "n" is typically your input size (or if it's not, you need to clearly define what it is). "n" is unlikely to ever be "number of vowels in the English alphabet" because that's a constant, that doesn't change at all when input changes.

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

This only makes sense if you consider a `contains` method to only take the arguments passed inside of the parenthesis. But in actuality there is an implicit `this` argument too. Armed with this knowledge it becomes trivial to see how the total input to the function is `N + 1` values. `N` being the length of the function, and the `1` representing the thing we're searching for. Since constant values in complexity theory are handily ignored we get an input of size `N`.

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.

Are you saying that because (JavaScript!) functions have a "length" property representing number of arguments, they are all O(N) (or greater)? (btw I don't see how "this" fits in here.)

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!

> You'll be hard pressed to find anyone anywhere that claims array.includes or string.indexof or list.contains and such are O(1)!

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.

> When your N is fixed (or even upper bounded), then it is always O(1).

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

Yeah I was working on an elevator control problem and made mention about how this doesn't have great time complexity, but the number of floors is surely less than 163.

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.

Another way to look at it: If A is a constant array and part of the program - and not an input, A.includes(x) is just a shorthand for a switch-case statement.

Linear search is O(n), but here, n is 5, and O(5) is O(1).

array.includes(x) is really a function includes(array, x), and this is O(n,1).

I've never seen Landau's notation with two variables, I don't think it exists. At best you could say it is O(n)*O(1) which is formally equivalent to O(n).

You can easily extend Landau's notation to multiple variables (or rather functions of multiple arguments). It's even pretty commonly done, eg a common statement is something like "Getting the k largest elements out of an unsorted input of n elements, takes O(k log n) time, if you use a heap."

> 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.

>You can easily extend Landau's notation to multiple variables [...] O(k log n)

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.

First, the usual way of just writing O(1) or O(n) or O(n^2) is kind of an abuse of notation.

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

You sound like my teacher.

This is pedantic, you are purposely using an unreasonable interpretation of "it's actually O(n)".

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.

I disagree, precisely because of your last sentence. The only meaningful interpretation of the proposed `isVowel` function is O(1), unless you want to accommodate arbitrary definitions of what characters are considered vowels.

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?

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 .

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

> In that case, wouldn't any implementation be O(1) regardless of whether they use an array, linked list, hashtable, heap, stack, whatever?

Yes.

Your statement about char I disagree with. A char is a byte, as you say. But that means it has numerical value as well. I could have a "identityMatrix" function that takes a char (because I decide I won't have matrices with a dimension > 256); it would be O(n^2) in operation though. In fact, I could have a 3 dimensional identity matrix creation function, and then it would be O(n^3). I could have a brute force generation of all possible permutations of the numbers 0-input, and now it's O(256!). The input of the function does not tell you anything about the complexity of the function (though it may tell you the max value of N. But, for instance, a function of O(n!) is almost assuredly going to be far, far worse than one with O(1), even if the size of N is maximally 256).

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.

Computational complexity theory is all about being very pedantic, and GP's conclusion is spot on.

Reply on news.ycombinator.com