3 ms·

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 nee

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!

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!