What is the time complexity of new Array(n).fill('apple') in JavaScript?-CodePudding

I was searching for the answer to this question but was not able to find any.

What is the time complexity of new Array(n).fill('apple')?

For n=5, this will create an array with 5 'apple' strings: ['apple', 'apple', 'apple', 'apple', 'apple']

My assumption is new Array(5) will first create an array with 5 empty slots and then iterate through it to put 'apple' in each slot. In this case, the time complexity is O(N), N is the length of the array?

However, I also hear that some say that since it's a built-in method, it will only take O(1).

CodePudding user response：

For larger arrays, nodejs shows approximately O(n) when you measure it (see code and results below).

I run this test app with 5 sizes for the array.

const sizes = [1000, 10000, 100000, 1000000, 1000000];

And, time how long it takes with process.hrtime.bigint(). I then output the total time for each sized array in nanoseconds and the per element time.

This is the output I get:

Array sizes:
 [ 1000, 10000, 100000, 1000000, 1000000 ]
Ns per pass:
 [ 36700n, 48600n, 553000n, 5432700n, 5268600n ]
Ns per element:
 [ 36.7, 4.86, 5.53, 5.4327, 5.2686 ]

You can see that the last three sizes are very close to O(n) with around a 5% variation from a fixed time per element (which would be exactly O(n)). The first one is way off and the second one is slightly faster per element than the others, though in the same general ball park as the last three.

The very first pass must have some sort of interpreter overhead (perhaps optimizing the code path) or perhaps just the overall overhead of the operation is so much more than actually filling the array that it distorts what we're trying to measure.

Here's the code:

class Measure {
    start() {
        this.startTime = process.hrtime.bigint();
    }
    end() {
        this.endTime = process.hrtime.bigint();
    }
    deltaNs() {
        return this.endTime - this.startTime;
    }

    deltaNumber() {
        return Number(this.deltaNs());
    }
}

const sizes = [1000, 10000, 100000, 1000000, 1000000];
const benchmark = new Measure();
const times = sizes.map(size => {
    benchmark.start();
    new Array(size).fill('apple');
    benchmark.end();
    return benchmark.deltaNs();
});
console.log('Array sizes:\n', sizes);
console.log('Ns per pass:\n', times);
let factors = times.map((t, index) => {
    return Number(t) / sizes[index];
});
console.log('Ns per element:\n', factors);

CodePudding user response：

You should ignore the algorithm complexity when you work with array of strings with 5 items length. But in this case you fill array with the same values. In this case:

Array(5).fill('apple')

is more elegant solution by code style reasons