So lets get to it!
To start off I'll be talking about Arrays. This is a Data Structure, most programmers are familiar with, that organizes data sequentially like shown below.
let basket = ['🥧', // 0 index '🍤', // 1st index '🍇', // 2nd index '🍒', // 3rd index '🍏', // 4th index '🍎'] // 5th index
When using arrays these are some common methods that have varying time complexities:
- Access the i-th Element O(1) - Constant Time: Since we are essentially accessing the the key: which is the index and the value which is the data stored in that index.
- Search O(n) - Linear Time: Since we have to use the index to access the value we wont be able to just instantaneously access a value and instead we will have to loop through n items of the array to get a certain value.
- Override the Element at i-th index O(1) - Constant Time: Similar to accessing the i-th Element all it takes is using the key: index to change the value at a certain index.
- Traverse All Elements O(n) - Linear Time: Looping through each element is similar to searching so we will be going through however many n items are in the array.
- Insertion O(n)* - Linear Time: Order matters in an array so if you insert an element in any index that isn't the last index you will have to shift the indexes after and increase their index number by 1. The act of shifting the indexes increases the time complexity to O(n) items needing to be shifted.
- Deletion O(n)* - Linear Time: Similar to above except you will have to shift the indexes after by decreasing their number by 1.
*Note - You do not have to shift the indexes if you are inserting to the end of the array or deleting the last index.
As the name implies pop() will delete a index from the end of the array reducing the size. While push() will add to the end of the array increasing the size. Both of which are constant time.
So Imagine you have a deck of cards:
A good time to use an array could be if you are creating a card game where you are only getting cards from the end of the deck. This will allow you to utilize the O(1) time complexity of pop() and push() to get cards from the top of the deck. Also In a deck of cards the order in which you put the cards matters so it will also be represented by the indices of the array.