4 ms·

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

virgilp 6y ago
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).
- herbstein 6y ago
  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.
  - adamisom 6y ago
    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!
tetha 6y ago
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.
F-0X 6y ago
array.includes(x) is really a function includes(array, x), and this is O(n,1).
- Znafon 6y ago
  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).
  - eru 6y ago
    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_variables https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variab... for more details.
    - Znafon 6y ago
      >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 https://math.stackexchange.com/a/2317054 for an example of demonstration.
      - eru 6y ago
        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.)
twic 6y ago
Linear search is O(n), but here, n is 5, and O(5) is O(1).
tsimionescu 6y ago
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.
BeetleB 6y ago
> 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.
- X6S1x6Okd1st 6y ago
  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.
- Wowfunhappy 6y ago
  > 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!)
higerordermap 6y ago
You sound like my teacher.

virgilp 6y ago

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

herbstein 6y ago
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.
- adamisom 6y ago
  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!

tetha 6y ago

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.

F-0X 6y ago

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

Znafon 6y ago
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).
- eru 6y ago
  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_variables https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variab... for more details.
  - Znafon 6y ago
    >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 https://math.stackexchange.com/a/2317054 for an example of demonstration.
    - eru 6y ago
      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.)

twic 6y ago

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

tsimionescu 6y ago

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.

BeetleB 6y ago

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

X6S1x6Okd1st 6y ago
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.
Wowfunhappy 6y ago
> 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!)

higerordermap 6y ago

You sound like my teacher.