Understanding how objects and arrays work through the lens of Big O is an important thing to know, as it should influence the choices you make when structuring data in your apps. Along with this, is it just as useful to know when you should be using an Object and when you should be using an Array.
Objects
When to use objects
- When you don't need order
- When you need fast access/insertion and removal
Big O of Objects
- Insertion: O(1)
- Removal: O(1)
- Searching: O(N)
- Access: O(1)
Searching is O(N) because here we are searching for a value in the object, rather than searching for a key. So to find the value, we must check every value in the object.
Big O of Object methods
- Object.keys: O(N)
- Object.values: O(N)
- Object.entries: O(N)
- hasOwnProperty: O(1)
Arrays
When to use arrays
- When we need order
- When you need fast access/insertion and (sometimes) removal
Big O of Arrays
- Insertion - it depends
- Removal - it depends
- Searching: O(N)
- Access: O(1)
Why does Insertion vary?
Because insertion at the end of the array (with array.push) is O(1). However if we want to insert at the beginning of an array (with array.unshift), it's O(N) as we have to move every entry up by one.
Why does Removal vary?
Because removal from the end of the array (with array.pop) is O(1). However if we want to remove from the beginning of an array (with array.shift), it's O(N) as we have to move every entry down by one.
Big O of Array methods
- Push: O(1)
- Pop: O(1)
- Shift: O(N)
- Unshift: O(N)
- Concat: O(N)
- Slice: O(N)
- Splice: O(N)
- Sort: O(N log N)
- forEach: O(N)
- Map/Filter/Reduce: O(N)
Conclusion
Hopefully this short article has given you a rough guide as to how performant Array methods and Object methods are, as well as when it would make sense to use one data structure over another. There's definitely more things to consider, but thinking about some of the points raised here will help you to make better decisions as a software developer.
