The Big-O of Objects and Arrays

Exploring best practices of the runtime complexities in objects vs arrays

The Big-O notation is an important tool for software engineers, evaluating the runtime of a function based on the time and space complexities. That being said, how do we determine in a general sense, the best way to manipulate or access properties of an object?

Objects are unordered data structures in key/value pairs. Because objects are unordered, without an index, it is faster and more efficient in performance.

let dog = {
    firstName: "Cocoa",
    breed: "Golden Retriever",
    age: 7,
    vaccinated: true
}

Since I am not concerned about having an ordered data structure, I can simply insert new key/value pairs, performing big-o of 1, constant time:

dog.owner = "Grace"
=> "Grace"
dig
=> {firstName: "Cocoa", breed: "Golden Retriever", age: 7, vaccinated: true, owner: "Grace"}

I can also simply delete a property, performing big-o of 1, constant time:

delete dog['owner']
=> true
dog
=> {firstName: "Cocoa", breed: "Golden Retriever", age: 7, vaccinated: true}

Searching and accessing properties in an object require the machine to go through all the key/value pairs so depending on the number of properties in an object(n), it will perform at a rate proportionate to n, big-o of n, linear time.

dog["firstName"]
=> Cocoa 

Big-O object methods generally perform big-o of n, creating an array based off of the data inside of the object.

Object.keys(dog)
=> (4) ["firstName", "breed", "age", "vaccinated"]
Object.values(dog)
=> (4) ["Cocoa", "Golden Retriever", 7, true]
Object.entries(dog)
=> (4) [Array(2), Array(2), Array(2), Array(2)]
0: (2) ["firstName", "Cocoa"]
1: (2) ["breed", "Golden Retriever"]
2: (2) ["age", 7]
3: (2) ["vaccinated", true]
length: 4

However hasOwnProperty performs big-o of 1, constant time, calling the method on the object and returning a boolean.

dog.hasOwnProperty("firstName")
=> true

Arrays are ordered data structures with an index. When you add or remove an element to the end of an array, you just add another index to the array. However, when you try to add or remove an element to the beginning of an array, you have to reindex the whole array.

let students = ["Grace", "Emily", "Carla"]
//index          0.         1.       2.
//adding and removing a student at the end of an array is simple
students.push("Juan") => add to end of array
students.pop("Juan") => remove at end of array
let students = ["Grace", "Emily", "Carla", "Juan"]
//index           0.       1.        2.       3.
let students = ["Grace", "Emily", "Carla"]
//adding and removing a student at the beginning of an array requires reindex
students.unshift("Juan") => add at beginning of array
students.shift("Juan") => delete at beginning of array

let students = ["Juan", "Grace", "Emily", "Carla"]
//index           0.       1.       2.       3.
let students = ["Grace", "Emily", "Carla"]

Adding and removing an element at the end of an array performs big-o of 1, constant time. However adding or removing an element to the beginning of an array performs big-o of n, linear time because it is dependent on n and grows in proportion to the size of the array.

If you do not need an ordered data structure, go with objects because they perform faster and efficiently, requiring less operations. However if you need an ordered data structure, best practices goes towards manipulating the array from the end to avoid reindex the whole array.