Big O Performance of Arrays and Objects in JavaScript

Performance

The efficiency of the program would be directly relying on Time Complexity when we deal with a huge amount of data to perform operations like searching, sorting, access, insertion and removal of an element.

We could selectively use objects and arrays based on the need to enhance the performance. We take the help of Big-O notation to compare and contrast the runtime for arrays and objects to understand them clearly.

Let us understand the concept of Big-O notation quickly in terms of time complexity.

Big-0 notation helps in calculating the efficiency of an algorithm formally.

To compare algorithms, we should not consider:

• Execution times — as they are specific to a particular computer.
• Number of statements executed — as it varies with programming language.

The ideal way of comparing algorithms is by calculating the number of operations the computer has to perform based on the size of an input.

Let us see it by a simple example. Calculate the sum of all numbers from 1 up to (and including) some number n.

Inefficient solution:

Here the number of operations increases as input(n) size increases.

Efficient solution:

Here the number of operations remains the same no matter what the input size is.

So, we can define the Big-0 notation by saying that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases.

f(n) could be linear (f(n) = n).

function addUpTo(n) {
let total = 0;
for (let i = 1; i <= n; i++) {  // O(n)
 total += i;
}
return total;
}

f(n) could be constant (f(n) = 1).

function addUpTo(n) {
return n * (n + 1) / 2; // O(1)
}

f(n) could be quadratic (f(n) = n²). See the below example. Here when the input size increases the number of operations will increase quadratically as there were for loop 0(n) inside for loop O(n). O(f(n)) * O(f(n)) = O(f(n²))

function printAllPairs(n) {
 for (var i = 0; i < n; i++) {  // O(n)
  for (var j = 0; j < n; j++) { // O(n)*O(n)
  console.log(i, j);
  }
 }
}

Now let us understand how objects and arrays work through the lens of Big-O.

Objects will be used when we need fast access, insertion and removal of an element as objects are comparatively much faster than the arrays in case of insertion and removal.

Big-O of Objects:

• Insertion — O(1)
• Removal — O(1)
• Access — O(1)
• Searching — O(n)

Big-O of Object methods:

• Object.keys — O(n)
• Object.values — O(n)
• Object.entries — O(n)
• hasOwnProperty — O(1)

Arrays will be used when we need orders. But working with the array is costly as insertion of an element at the beginning and removal of an element is not so easy as the index has to reset for an entire array. Say the size of an array is one thousand, then one thousand operations have to be done after insertion at the beginning to reset the indexes. There are more efficient data structures and algorithms for that.

Big-O of Arrays:

• Insertion — It depends. Insertion at the end is O(1). But insertion at the beginning is o(n)
• Removal — It depends. Removal at the end is O(1). But in between or at the beginning is o(n)
• Access — O(1)
• Searching — O(n)

Big-O of Array methods:

• push, pop — O(1)
• shift, unshift, concat, slice, splice — O(n)
• forEach/map/filter/reduce/etc. — O(n)

Let us understand it with a simple example. Write a function that accepts two arrays and returns true if every value in the array has its corresponding value squared in the second array. The frequency of values must be the same.
frequency_function([1,2,3], [4,1,9]) //returns true
frequency_function([1,2,3], [1,9]) //returns false

Below is the Array based approach.

function frequency_function(arr1, arr2){  
   
 if(arr1.length !== arr2.length) return false;
 for(let i = 0; i < arr1.length; i++){         
  let correctIndex = arr2.indexOf(arr1[i] ** 2)    
  if(correctIndex === -1) {             
   return false;         
  }         
  arr2.splice(correctIndex,1)      
 }     
 return true;
}

Here O(f(n)) is n² as inside for loop (O(n)) the indexOf method is O(n) as it will search from the beginning and splice method is also O(n) as it has to reset the index. That is for each element in arr1 n operations has to be done for arr2. If the array size is 100, then 100*100*100 which is equal to 1000000 operations will be performed. So here when n increses the number of operations increase quadratically.

Below is the Object based approach:

function same(arr1, arr2){     
 if(arr1.length !== arr2.length){         
  return false;     
 }     
 let frequencyCounter1 = {}     
 let frequencyCounter2 = {}     
 for(let val of arr1){         
  frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1     
 }     
 for(let val of arr2){         
  frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1   
 }
 for(let key in frequencyCounter1){         
 if(!(key ** 2 in frequencyCounter2)){             
   return false         
 }          
 if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){  
   return false
  }     
 }      
 return true;
}

Here we are converting the two arrays in to two objects and then we are checking for the corresponding squared values. We have three separate O(n) operations. That is if the input array size is 100, then 100+100+100 is equal to 300 operations will be performed. So here when n increses the number of operations increase linearly.

Conclusion

So as you can see working objects is comparatively much faster than the arrays when we don’t need orders.

I hope you have found this useful. If so, please be sure to let me know in the comments. Happy coding!

More content at plainenglish.io