Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

163
Visualizações
What is the time complexity of new Array(n).fill('apple') in JavaScript?

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).

about 4 years ago · Juan Pablo Isaza
2 Respostas
Responde à pergunta

0

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

P.S. O(1) + O(n) => O(n)

about 4 years ago · Juan Pablo Isaza Relatório

0

The time complexity should be O(N) as it should scale linearly with the length of the array.


To test out that theory, I ran some benchmarks just to see if it appears to actually be O(n).

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);
about 4 years ago · Juan Pablo Isaza Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda