Search code examples
javascriptarraysbig-ojavascript-objects

Big O of all javascript array and object methods

Hey guyz currently I am studying the concepts of Big O ,I would like to clear my few question, I am well aware of Big O and its concept but still I couldnt find any proper answer on google related to these questions
1. What is Big O of all the javascript array method ( specially indexof , includes)
2. What is big O of all javascript object method ( specially keys,values)
3. Big o(1) is said to be constant time but what is exact time in terms of ms

Solution
    1. What is Big O of all the javascript array method ( specially indexof , includes)

    Looking up values in unordered lists is a classical O(n) task: as you do not know where the element is, you just have to start checking them one by one. While technically it is possible to create an "inverse", value->key map for arrays, environments usually just do not do that. For example the V8 engine is not an exception either, see https://github.com/v8/v8/blob/master/src/elements.cc, methods like IndexOfValueSlowPath

    for (uint32_t k = start_from; k < length; ++k) {

    or IndexOfValueImpl

    for (uint32_t k = start_from; k < length; ++k) {

    and a couple more instances of them.
    They are called from Runtime_ArrayIndexOf, at line 899 specifically. If this method does not apply, there is a fallback a couple lines later, again using a simple for loop (index is set earlier, already used for calling the methods mentioned above):

    for (; index < len; ++index) {
    1. What is big O of all javascript object method ( specially keys,values)

    Object is in the neighboring (to array) runtime file, https://github.com/v8/v8/blob/master/src/runtime/runtime-object.cc, but do not expect magic there either, it also ends up in various for loops in https://github.com/v8/v8/blob/master/src/keys.cc, like a simple one checking if an array is built of valid keys (numbers and strings)

    static bool ContainsOnlyValidKeys(Handle<FixedArray> array) {
  int len = array->length();
  for (int i = 0; i < len; i++) {
    Object e = array->get(i);
    if (!(e->IsName() || e->IsNumber())) return false;
  }
  return true;
}

    or another one called from various places to build a single collection from multiple sources:

    void KeyAccumulator::AddKeys(Handle<FixedArray> array,
                             AddKeyConversion convert) {
  int add_length = array->length();
  for (int i = 0; i < add_length; i++) {
    Handle<Object> current(array->get(i), isolate_);
    AddKey(current, convert);
  }
    1. Big o(1) is said to be constant time but what is exact time in terms of ms

    There is no such thing.