adafia

Brief Performance Analysis of Arrays and Objects through the lens of Big O Notation.

Samuel Adafia's photo
Samuel Adafia
·

6 min read

Deciding which data structure to use during software development can be challenging. This blog seeks to help you make a decision when it comes to the built-in data structures in JavaScript, objects and arrays. Their performance will be analysed by taking a close look at how common interactions like data access, insertion, removal and search are done with each of them.

Table Of Contents

Prerequisites

Objectives

  • Understand how objects and arrays work through the lens of Big O Notation.
  • Explain why adding elements to the beginning of an array is an expensive operation with respects to space and time.
  • Compare and contrast the runtime for arrays and objects, as well as their built-in methods.

Objects

Objects in JavaScript are unordered data structures of key-value pairs. This means that there's no beginning or end of an object. When data is added to an object, the data is placed anywhere within it.

const person = {
  name: 'Kwame',
  age: 30,
  height: 182,
  hobbies: ['reading', 'drawing', 'running']
}

Objects are most valuable when order is not needed but quick data access, insertion and removal are of priority.

Data Access, Insertion and Removal

Through the lens of Big O Notation, data access which involves retrieving or modifying data stored in an object is done in constant time O(1). This is also true for the insertion and removal of data.

  • insertion - O(1)
  • removal - O(1)
  • access - O(1)

Searching in Objects

Searching within objects, on the other hand, is linear time O(n). Searching here does not refer to looking for a key like age in our example object above. It refers to checking through all values of the object to see if a provided search query exists. For example, checking to see if any of person object values include the word run.

Object Methods

Accessing all the keys of an object through Object.keys() is O(n) because it's runtime is directly proportional to the number of keys the object has. The same applies to the instance of accessing an object's values with Object.values(). It's technically more work but its notation can be approximated toO(n). Retrieving all entries of an object with Object.entries() technically involves a lot more computation than accessing keys and values because it has to compile keys and values in an array. However, its complexity can be rounded up to O(n). Finally, in checking to see if an object has a property or not with in-built method hasOwnProperty() is constant time O(1). This is because it just checks for the existence of a property and returns a boolean.

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

Arrays

Out of the box, arrays are ordered lists. Each element in an array is assigned an index (a numerical value that corresponds to the elements storage location in memory). The ordered feature of arrays come at a cost of performance optimization so arrays should be used when the order of the data you are storing in them is important.

Data Access

Operations that involve access (retrieving or updating data) are fast, they have a big O of constant time O(1). This is as a result of the indexing feature of arrays. Accessing an element in an array with an index of 0 takes the same time to access an element with an index of 1000.

Searching in Arrays

Searching, on the other hand, is linear O(n). If I wanted to find out if orange is an element of an array of fruits, I would have to check potentially every single element. Hence the time it will take me to do that is directly proportional to the number of elements in the array. However, you can achieve a big O of O(log(n)) when searching through an array. To achieve this, two things will have to happen. The first condition is that the array has to be sorted. Secondly, you would have to employ a binary algorithm in searching through the sorted array. This is because in using a binary search algorithm, the number of things to search through is halved in every iteration until the element you are looking for is found. Unsorted arrays, on the other hand, can only be searched using a linear search method hence will maintain a runtime of O(n) also known as linear time.

Insertion & Removal of data

When it comes to insertion and removal, it depends on where the data is being inserted or removed. This is a result of the ordered nature of arrays.

Inserting elements at the end of an array using the push() method has a big of Constant time O(1). This is because javascript looks at the index of the last element and adds the new element with an index equivalent to the numerical value of the last index plus 1. On the other hand, inserting an element at the beginning of the array is linear time O(n). This is because all the existing elements in the array will have to be re-indexed. The same principles apply in removing elements from an array. In summary, using push and pop is always faster than using shift and unshift.

Array Methods

The big O of a few of the standard built-in methods of arrays have already been discussed in the above paragraphs (push, pop, shift and unshift).

  • push: O(1).
  • pop: O(1).
  • shift: O(n).
  • unshift: O(n)

Other methods are concat, slice, splice and all the higher-order functions. (forEach, map, filter, reduce, etc). Below are their respective performance analysis based on big O.

  • concat: O(n). (adding or merging two arrays)
  • slice: O(n). (returns a copy of part or all of an array)
  • splice: O(n). (remove or add elements anywhere in an array)
  • forEach / map / filter / reduce / etc.: O(n).

For more information on how each of these work, you can refer to MDN web docs.

Conclusion

  • Objects are faster at pretty much everything but have no order.
  • Arrays are good when you need ordered data.
  • In working with arrays, unless absolutely necessary, avoid adding and removing elements to/from the beginning of an array.
JavaScriptObjectsarraysperformance