Complexity analysis

Overview

An array organizes items sequentially, one after another in memory. Each position in the array has an index, starting at 0.

Strengths:

• Fast lookups. Retrieving the element at a given index takes $O(1)$ time, regardless of the length of the array.
• Fast appends. Adding a new element at the end of the array takes $O(1)$ time.

Weaknesses:

• Fixed size. You need to specify how many elements you’re going to store in your array ahead of time. (Unless you’re using a fancy dynamic array.)
• Costly inserts and deletes. You have to “scoot over” the other elements to fill in or close gaps, which takes worst-case $O(n)$ time.

The following are an array’s standard operations and their corresponding time complexities:

• Accessing a value at a given index: $O(1)$
• Updating a value at a given index: $O(1)$
• Inserting a value at a given index: $O(n)$
• Inserting a value at the end:
  • amortized $O(1)$ when dealing with a dynamic array
  • $O(n)$ when dealing with a static array
• Removing a value at the beginning: $O(n)$
• Removing a value in the middle: $O(n)$
• Removing a value at the end: $O(1)$
• Copying the array: $O(n)$

Inserting

If we want to insert something into an array, first we have to make space by "scooting over" everything starting at the index we're inserting into.

In the worst case we're inserting into the 0th index in the array (prepending), so we have to "scoot over" everything in the array. That's O(n) time.