JavaScript Arrays With Big O Complexities!

Array is the most commonly used data structure in JavaScript. But, what is it exactly? And if you’re looking from the data structure point of view, you’d like to know about the Big O complexities as well. So, let me tell you what they are and each of their complexities.

In JavaScript, an array is an ordered list of data in which each element can be efficiently located by its index.

You define an array by using the square brackets ([ ]) notation.

let anArray = []; //empty array
let filledArray = [1, "Hello", "World"] //filled array

Here are the characteristics of arrays in JavaScript :

• Arrays are dynamically sized. Unlike other programming languages where you have to allocate a specific size when defining an array, you can just define an array and its size will change depending on its content in JavaScript.
• Can contain mix of different data types. An array in JavaScript can contain numbers, strings or even another array in it. The data types in it don’t have to be uniform.
• Zero-indexed. Arrays are indexed starting from zero.
• Reference based. When you copy an array, you are actually not copying the content itself, but you are copying the reference to the content,
• Built in. You don’t have to built this data structure from scratch since it is natively available.

If you haven’t understood about Big O Natation to tell algorithm complexity, please check out this post first before going on.

Accessing Array

An array can be accessed by typing the array name followed by square brackets with the wanted index inside.

let anArray = [1, 2, 3, 4];

console.log(anArray[0]) //1

Accessing an array takes O(1) time complexity as it is constant and only involving one operation

Insertion

You can add or insert a new element to an array with the push or unshift method. The difference is that push adds an element at the end of the array but unshift adds an element at the beginning of the array.

let anArray = [1, 2, 3, 4];

anArray.push(5, 6); //[1, 2, 3, 4, 5, 6]

anArray.unshift(0); //[0, 1, 2, 3, 4, 5, 6] 

Insertion complexity depends on whether it is done at the end or the beginning of an array.

If it is done at the end (push), it takes O(1) time complexity.

But, if it is done at the beginning, the complexity is O(n) because arrays in JavaScript are basically objects. JavaScript would have to change the reference for each of the elements, placing the new element to index 0, moving the previously first element to index 1 and so on. So in the end, there are n operations done.

Deletion

You can delete an element from an array with the pop and unshift method. Pop deletes the last element of your array and unshift deletes the first element of your array. When called, both functions return the deleted elements.

let anArray = [1, 2, 3, 4];

anArray.pop(); //return 4; anArray=[1, 2, 3]

anArray.shift(); //return 1; anArray=[2, 3] 

For the same reasons as insertion, deletion at the end (pop) is O(1) and deletion at the beginning is O(n).

Iteration

There are cases where you want to iterate through an array like modifying each elements of the array or searching for a specific element. You can do it by looping through the array with for or while clauses.

for loops

for is very commonly used to loop through an array. There are also additional variations that help to make looping easier.

// for loop : looping by setting the conditions
for (let index = 0; index < array.length; index++) {
    const element = array[index];
    // code here
}

// for in : looping by accessing each index of array 
for (const index in array) {
    const element = array[index];
    // code here
}

// for of : looping by accessing each element of array
for (const element of array) {
    // code here
}

// for each : syntactic sugar of for of
array.forEach(element => {
    // code here
});

while loops

The while loops work just like the for loops but they only use conditions for evaluations. Conditions must evaluate to true or false and the looping only stops when the condition is false.

There are 2 variations: while and do while. While evaluates the condition first but do while runs your code first then evaluates it. So, do while will run your code at least once.

while (condition) {
    //code here
}

do {
    //code here
} while (condition);

// example
let cond = true;
while (cond === true) {
    cond = false; //looping stops
}

With iteration, you have to go through n elements and doing operations on each of them. So the complexity is O(n)

Additional Note

Those are generally the expected complexities for each of the methods. As JavaScript runs on browser, the exact way arrays perform depends on the browser itself. So, the complexities might differ from browser to browser. But these complexities are what you might expect generally.

Summary

Those are the explanation of the fundamental array methods that you need to understand to understand JavaScript and DSA (Data Structures and Algorithms) more. Below are the recapped table of the complexities.

Complexities

Hope you understand more now! You can go and explore more advanced methods like map, filter, reduce, etc and try to tell the complexities. If you want me to cover those too, please comment below!

For an exercise and explanation on array topics, you can read How To Rotate A Matrix In JavaScript.

For you who want to brush up your JavaScript skills, whether to deepen or learn form zero, I recommend you try Codecademy. There are tons of JavaScript lessons that you can learn in a structured and interactive way. You can learn from the most basic materials to advanced stuffs and even preparing for technical interviews. Go try it now!

There are also algorithm and Computer Science or Interview Prep resources on codecademy. So go check it out if you’re interested!

W3schools is also an amazing resource for JavaScript references. But it is more of a technical reference and doesn’t cover about complexities. You can check out the rest of my blog and upcoming posts to learn more!

If you have any questions or suggestions, please do comment below!