Javascript Arrays and Big-O

Javascript Array for any examples in this article

When to use arrays

• when you need to sort/order your data

Big-O

• Search: O(N)

As the array grows, it’ll take longer to go through every element in the array and search for the element that matches the search criteria.

• Access: O(1)

Arrays have indices, so it’s quick to access a specific element in the array.

• Insert/Remove: It depends on where the element is being inserted/removed.

If I add/remove from the end, it’s O(1). The indices of the original array didn’t change. If I were to do trainers.push(“Serena”), the trainers array is now [“Ash”, “Brock”, “Misty”, “May”, “Max”, “Serena”]. The computer doesn’t have to go back and edit the indices.

If I add/remove from the beginning, it’s O(N). The indices of the original array have to change. If I were to do trainers.unshift(“Serena”), the trainers array is now [“Serena”, “Ash”, “Brock”, “Misty”, “May”, “Max”]. trainers[0] used to be “Ash” but now it has to be “Serena” due to the destructive change.

Javascript Array Methods

push()/pop()

These methods deal with the end of the array, so the indices do not have to be rearranged from the beginning. They have O(1).

shift()/unshift()/concat()/slice()/splice()

These methods deal with changing the indices of the existing or give you a new array, so they have O(N).

forEach()/map()/filter()/reduce()

These methods iterate through the array, so it scales with the number of elements in the array. Thus, they have O(N).

sort()

This is O(N * log N). This is the optimal runtime for most cases.