Menu
Does indexOf simply walk through the array or does it do something that is faster? I know that this is implementation dependent but what does Chrome or Firefox do?
451
indexOf() – also runs in linear time. It iterates through the internal array and checks each element one by one, so the time complexity for this operation always requires O(n) time.
unshift() has a Linear Time Complexity and is O(n). The Array. pop() and Array. shift() methods which are used to remove an element from the end and beginning of an array respectively, work similarly.
The time complexity of the filter function is O(n) as well. At this moment, the total time complexity is O(2n). The last step is reduce function. We apply the result of the filter function to reduce function.
Because it takes a single step to access an item of an array via its index, or add/remove an item at the end of an array, the complexity for accessing, pushing or popping a value in an array is O(1). Whereas, linearly searching through an array via its index, as seen before, has a complexity of O(n).
The most efficient way to find the first index matching a value in an unsorted array is to just walk through the list in order, which is O(n). MDN also has some hints:
Returns the first index at which a given element can be found in the array, or -1 if it is not present.
[...]
fromIndex
Default: 0 (Entire array is searched)
The index to start the search at. If the index is greater than or equal to the array's length, -1 is returned, which means the array will not be searched. If the provided index value is a negative number, it is taken as the offset from the end of the array. Note: if the provided index is negative, the array is still searched from front to back. If the calculated index is less than 0, then the whole array will be searched.
In case you're wondering, here's how WebKit implements it:
EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec) { // 15.4.4.14 JSObject* thisObj = exec->hostThisValue().toThis(exec, StrictMode).toObject(exec); unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec); if (exec->hadException()) return JSValue::encode(jsUndefined()); unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length); JSValue searchElement = exec->argument(0); for (; index < length; ++index) { JSValue e = getProperty(exec, thisObj, index); if (exec->hadException()) return JSValue::encode(jsUndefined()); if (!e) continue; if (JSValue::strictEqual(exec, searchElement, e)) return JSValue::encode(jsNumber(index)); } return JSValue::encode(jsNumber(-1)); } If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
