Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

93
Views
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 answers
Answer question

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 Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!