Hacker News Reader

Comment by Znafon | Hacker News Reader

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.

View on HN

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