The algorithm behind js indexOf() method in JAVASCRIPT

Question

When solving https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ problem, I found out that using indexOf method gives us the favor of polynomial performance. But as mentioned here, if we use this polyfill to determine index of element, it generates time limit error. My concern is what is the exact implementation of indexOf method for which it can perform in constant time which I am guessing close or equal to(0[1])?

Answer 1

indexOf does not run in constant time. It is expected that it runs much faster than a polyfill implementation in JavaScript. This is because the functions that are part of the JavaScript language (EcmaScript), are typically written in a lower level language like C or C++.

Here is a test that illustrates that indexOf does not run in constant time:

// create a very long string aaaa...ab...bc...cd (etc)
let alpha = "abcdefghijklmnopqrstuvwxyz";
let s = Array.from(alpha, c => c.repeat(10000000)).join("");
// find each of the letters in this long string
for (let c of alpha) {
    let start = performance.now();
    s.indexOf(c);
    let end = performance.now();
    console.log(end-start);
}

See What language is JavaScript written in? for what languages are used for implementing JavaScript, including functions like indexOf.

Answer 2

Your problem is just a range-minimum query problem, which can be solved with constant time complexity using sparse tables. But with the fact, that there are only 4 different values there is an easier way to solve it:

Pre-calculate the number of times each letter appears on each prefix (first n symbols). This preprocessing will be done in linear time. Then for your range check if there is, for example, A letter as follows: if the count of letters before the start is equal the count of letters before the end - then, there is no letter A in this range. Do the same for all 4 letters and pick the minimum.