What is Big O?
Big O notation help us for measuring the rate of growth of an algorithm and describes mathematically the complexity in the worst case. The measuring refers to number of operations it takes to complete the task.
The O is short for 'Order of'. So, if we’re discussing an algorithm with O(n^2), we say its order of, or rate of growth, is n^2, or quadratic complexity.
Let's see the constant, linear and quadratic and javascript examples.
O(1) — Constant Time
Given an input of size n, it only takes a single step for the algorithm to accomplish the task.
Examples: accessing and specific array index, pushing one element in array, insertion in queue.
https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dhc1mritfulvvb7lr55x.png
const tripleNumber(number) => {
return number number*3;
}
O(n) — Linear Time
Given an input of size n, the number of of steps required is directly related (1 to 1)
Examples: linear search and traversing and array.
fruits = ['banana', 'apple'];
const findApple = (array) => {
for( let i=0; i < array.length ; i++){
if(array[i] === 'apple')
return true;
}
return false;
}
O(n²) — Quadratic Time
Given an input of size n, the number of steps it takes to accomplish a task is square of n.
Examples: bubble sort and traversing a matrix (2D array).
let matrix = [[0,1], [6,2]];
const getAllElementsMatrix = (matrix) => {
for( let i=0; i < matrix.length ; i++){
for( let j=0; j < matrix.length ; j++){
console.log(matrix[i][j])
}
}
}
If we have more n elements, more operations we are going to do:
const large = new Array(1000000000).fill('apple');
const findApple = (array) => {
for( let i=0; i < array.length ; i++){
if(array[i] === 'apple'){}
console.log('Apple here!')
}
}
Try this, 1 billion os elements!
We can have a mix with this notations
Let's see an example in Javascript:
const numbers = [1,5,9,8]
const verifyAndReturn = (array) => {
const someNumbers = []
/* O(n) = O(4) because we have 4 elements
in the array */
for( let i=0; i < array.length ; i++){
if(array[i] % 2 == 0){
someNumbers.push(array[i])
}
}
/*O(1) because it iterate and get
the first element and returns it */
for( let i=0; i < someNumbers.length ; i++){
return someNumbers[0];
}
}
//The final will be O(4) + O(1) = O(5)
console.log(verifyAndReturn(numbers))
The final complexity as we can see in the code above will be O(4) + O(1) = O(5).
Let's see one more example:
const matrixNumbers = [[1,2], [3,5]]
const quadratic = (matrix) => {
const someNumbers = []
/*O(n^2) = O(2^2) because we have 2 sets
of elements in the matrix (4 elements)*/
for( let i=0; i < matrix.length ; i++){
for( let j=0; j < matrix.length ; j++){
someNumbers.push(matrix[i][j])
}
}
/*O(n) = O(4) because we have 4 elements
in the array from the before processing*/
for( let i=0; i < someNumbers.length ; i++){
//do Something
}
}
The final complexity will be O(2^2) + O(4) = O(8).
Any doubt?
Important link: https://www.bigocheatsheet.com/
Contacts
Email: luizcalaca@gmail.com
Instagram: https://www.instagram.com/luizcalaca
Linkedin: https://www.linkedin.com/in/luizcalaca/
Twitter: https://twitter.com/luizcalaca
Top comments (0)