The Big O is a notation that gives a general trend to analyse the performance of an algorithm based on time and space complexity.
Why is so important ? The World’s top tech companies test candidates knowledge of algorithms and the performance of these algorithms. Having an understanding of how your code is a crucial skill in programming.
For this first introduction we will cover O(1),O(n) and O(n2).
Notations
O(1) Constant time
It represents an algorithm run time is fixed. No matter the amount of the input data set, the algorithm will always take the same amount of time.
function(n){
n*n*n
}N might be 1 or a million, it won’t change the running time.
O(N) — Linear Time
O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
function(array){
for (let i = 0; i < array.length; i++){
console.log(array[i]);
}
}Longer the array will be, longer it will take for loop to go through. The performance of the algorithm is link to the length of the array.
O(N²) — Quadratic Time
O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set.
function(array){
for (let i = 0; i < array.length; i++){
for (let j = 0; j < array.length; j++){
console.log(array[j]);
}
}
}A nested loop is the prefect example of a quadric time .
Big O of objects
When you don’t need any ordering, objects are an excellent choice.
Insertion : Objects are unordered collection of data in a form of “key:value” pairs, there is no beginning and end so it doesn’t matter where you insert because there is no repercussion.
Removal : Same as insertion, removing an item from an object as no repercussion because the program won’t go through all items, it will directly access the key:value. It goes the same for Accessing, using the key will find the corresponding value.
Searching : The performance of searching for a value in object depends on the length. The program will need to go through all the value to find the matching one.
Big O of arrays
Array is a special variable, which can hold more than one value at a time and are listed by index.
Insertion/Remove: It depends ? Yes if you add or remove from the end, you won’t have to change all the index list , only the last one will be affected however if you add an item at a specific place you will have to go trough all the value to assign the new index. The performance will vary depending on the length.
Searching: To search for a value in your array, the program will go through every items and find which does correspond.
Access: Accessing an array won’t require to go through all the items by using the index, we are directly connected to the value .
