 What is an Array?
 Arrays & Big O Notation

Implementing an Array
 Push Method (Adding)
 Using
push
Method  Big O With
push
Method get
Method (Access) Using the
get
method.  Big O With
get
Method pop
Method Using the
pop
method  Big O With
pop
Method delete
Method Using
delete
method  Big O With
delete
Method indexOf
Method (Searching) Using
indexOf
method  Big O With
indexOf
Method unshift
Method Using
unshift
method  Big O With
unshift
Method
What is an Array?
Arrays or Lists are used to store data in memory Sequentially (In Order).
Arrays & Big O Notation
In JavaScript, Arrays are builtin Data Structures.
And there are Methods to Access, Push, Insert, and Delete Data.
Using Big O with these Methods will be:
 Access => O(1).
 Add => O(1).
 Insert => O(n).
 Delete => O(n).
 Searching => O(n).
Examples
const arr = ["a", "b", "c"];
// Add
arr.push("d");
console.log(arr); // ["a", "b", "c", "d"]
// Access
console.log(arr[0]); // a
// Insert
arr.unshift("X");
console.log(arr); // ["X", "a", "b", "c", "d"]
arr.splice(2, 0, "X");
console.log(arr); // ["a", "b", "X", "c"]
// Delete
arr.splice(1, 1);
console.log(arr); // ["a", "c"]
// Searching
console.log(arr.indexOf("a")); // 0
In order to understand where did these rules come from, We can implement our own Array.
Implementing an Array
We don't have to build an array in JavaScript, But it's very useful to do so in order to really understand why Big O is different from an operation to another with Arrays.
class List {
constructor() {
this.length = 0;
this.data = {};
}
}
Push Method (Adding)
push(ele) {
this.data[this.length] = ele;
this.length++;
return this.length;
}
 Adding the passed element to the
data
object as thelength
is the key.  Increment the length by 1.
 Return the length.
Using push
Method
const list = new List();
list.push(5);
console.log(list.data); // { "0": 5 }
Big O With push
Method
Let's use the roles of Big O to understand why adding an element in an array is O(1).
push(ele) {
this.data[this.length] = ele; // => O(1)
this.length++; // => O(1)
return this.length; // => O(1)
}
The number of operations will be O = 1 + 1 + 1.
Eventually, Big O with the Push Method will be O(1).
get
Method (Access)
get(index) {
return this.data[index];
}
Using the get
method.
const list = new List();
list.push(5);
console.log(list.get(0)); // 5
Big O With get
Method
This function only Returns the value of the given index.
get(index) {
return this.data[index]; //O(1)
}
Eventually, Big O with the Get Method will be O(1).
pop
Method
pop() {
const lastElement = this.data[this.length  1];
delete this.data[this.length  1];
this.length;
return lastElement;
}
 Store the last element in a variable
lastElement
.  Use the
delete
keyword to remove it from thedata
object.  Decrementing the length of the array by 1.
 Return the lastElement.
Using the pop
method
const list = new List();
list.push("a");
list.push("b");
list.pop();
console.log(list.data); // { "0": "a" }
Big O With pop
Method
pop() {
const lastElement = this.data[this.length  1]; //O(1)
delete this.data[this.length  1]; // O(1)
this.length; // O(1)
return lastElement; // O(1)
}
So, Big O with the pop method will be also O(1).
delete
Method
// Delete
delete(index){
const ele = this.data[index];
for(let i = index; i < this.length  1; i++){
this.data[i] = this.data[i + 1];
}
delete this.data[this.length  1];
this.length;
return ele;
}
We get the ele we want to delete.
Looping starting from the
index
, and replacing it with the next element.Deleting the last element of the array.
Decrementing the length by 1.
Returning the deleted element.
Using delete
method
const list = new List();
list.push("a");
list.push("b");
list.push("c");
list.delete(1);
console.log(list.data); // { "0": "a", "1": "c" }
Big O With delete
Method
// Delete
delete(index){
const ele = this.data[index]; // O(1)
for(let i = index; i < this.length  1; i++){
this.data[i] = this.data[i + 1]; // O(n)
}
delete this.data[this.length  1]; // O(1)
this.length; // O(1)
return ele; // O(1)
}
So, Big O with the delete method will be O(n).
indexOf
Method (Searching)
indexOf(ele) {
for (const i in this.data) {
if(this.data[i] === ele){
return i;
}
}
return 1;
}
 Looping through the object using for in.
 Check if the passed element exists.
 If yes return the index.
 If no as the normal indexOf we will return 1.
Using indexOf
method
const list = new List();
list.push("a");
list.push("b");
list.push("c");
console.log(list.indexOf("b")); // 1
Big O With indexOf
Method
indexOf(ele) {
for (const i in this.data) { // O(n)
if(this.data[i] === ele){
return i;
}
}
return 1;
}
Because we are Looping, the Big O will be O(n).
unshift
Method
unshift(ele) {
for (let i = this.length; i > 0; i) {
this.data[i] = this.data[i  1];
}
this.data[0] = ele;
this.length++;
}
 Looping backwards and shift every element to the next element.
 adding the passed element to the first index
0
.  Increasing the length by 1.
Using unshift
method
const list = new List();
list.push("a");
list.push("b");
list.push("c");
list.unshift("X");
console.log(list.data); // { "0": "X", "1": "a", "2": "b", "3": "c" }
Big O With unshift
Method
unshift(ele) {
for (let i = this.length; i > 0; i) {
this.data[i] = this.data[i  1]; // O(n)
}
this.data[0] = ele; // O(1)
this.length++; // O(1)
}
Because we are Looping, the Big O will be O(n).
Top comments (0)