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

94
Visualizações
Big O of Adding to an Empty Array

I understand it's constant to add to an empty array, but after the first element is added, doesn't the time shift to O(N)?

Similarly, does removing a single element from the middle of the array change the whole indexing of the array of just the left side (from n/2 to n )?

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

0

Adding to an Array often means allocating a new array of size n+1 and copying all the content. This takes O(N) time, if the array is empty (or in fact any fixed size, but practically any small size) you can call this O(1).

What most collection libraries do is provide a growable array like collection which is actually an Array and an extra integer size counter. When the underlying array is filled to capacity and we want to add another element we don't grow it by 1 but by some multiplicative factor(e.g 2, doubling it's size). This is done as above, allocating a larger array and copying content, preferably using page level efficient copying for larger arrays. This gives amortaized O(1) time for adding an element, but worst case O(N). N being the number of elements in the array.

If you remove an element from the middle of an array you may refer to an operation which shifts all data past that index back by one, or you might be refering to an operation which just sets that index to null or other empty value. The first is O(N) the second is O(1)

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