Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

167
Vistas
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 Respuestas
Responde la pregunta

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 Denunciar

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 Denunciar
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda