Time Complexity of ArrayList Insertion

Then calculate the average time complexity of inserting n new items into an empty brand new ArrayList.

Problem Statement

Explain how an ArrayList works in Java. Then calculate the average time complexity of inserting n new items into an empty brand new ArrayList.

Evaluation

  • The explanation of how an ArrayList allocates memory (25%)
  • The expanded mathematical calculation of the cost of insertion over time (25%)
  • Mathematical and order notation simplification (25%)
  • Correctness of the final O notation and the grand conclusion (25%)

References

Vlad, a software architect at Lionside, a Bay Area gaming startup, asked me this during an interview

Recommended reading

Author
Amin Ariana
Published
September 2010