// Big O and the official term is Big O. Asymptotic analysis.
/*
What is good code
1. Readable
2. Scalable (big O) -> code than can scale
How can we demonstrate the idea of code
*/
// const nemo = ['Nemo'];
// function findNemo(array) {
// for(let i = 0; i < array.length; i++) {
// if (array[i] === 'Nemo') {
// console.log('Found NEMO');
// }
// }
// }
// findNemo(nemo);
/*
* How can we measure the performance and the scalability of the code
* JavaScript can help us with some functions
*/
const nemo = ['Nemo'];
const large = new Array(100).fill('Nemo')
function findNemo(array) {
let t0 = performance.now();
for(let i = 0; i < array.length; i++) {
if (array[i] === 'Nemo') {
console.log('Found NEMO');
}
}
let t1 = performance.ddnow();
console.log('Call to find Nemo took', t1-t0);
}
findNemo(large);
/*
* Big O notation is the language we use to describe how long
* an algorithm took to run.
* When we talk about Big O and scalability of code, we simply mean
* when we grow bigger and bigger with our input, how much does the
* algorithm or function slow down.
* so we have a graph with Operations on the Y axis and Elements on the X axis
* meaning if the element increases how many more operation we need to do.
* and this is what we call algorithm efficiency and Big O allow us to explain
* this concept.
* The take home about this is that when we talk about Big O and scalability of
* code we simply mean, when we grow bigger and bigger with our input, how much
* does the algorithm slow down?
* So instead of using performance.now() to calculate our time to measure
* the efficiency of our function, we can just calculate how many operations
* a computer has to perform; because each operation takes time; so Big O
* allows us and concerns us with how many steps it takes in a function.
*/
/*
* What would be the Big O for this function.
*
* If we have 4 elements we have 4 operations, and if we draw a line
* is linear, this has big notation of
* O(n) --> linear time
* n can be anything but when it comes to Big O is a standard, the number
* of inputs.
* as the array increases it increases the number of operations.
* Big O doesn measure things in seconds, instead we are focusing on how
* quickly our runtime grows.
* We do this by using the size of the input which we call N, and compare to
* the number of opeartions that increase. This what scalability means.
*/
const nemo = ['Nemo'];
const large = new Array(100).fill('Nemo')
function findNemo(array) {
for(let i = 0; i < array.length; i++) {
if (array[i] === 'Nemo') {
console.log('Found NEMO');
}
}
console.log('Call to find Nemo took', t1-t0);
}
findNemo(large);
/*
* The first notation is O(n)
* O(n) --> linear time
* What happens if we have a function like the following
*/
function compressFirstBox(boxes) {
console.log(boxes[0]);
}
/*
How many steps or operations this function take.
If the boxes increase from 1 to 100 or 100000; what would happen?
This is what we call CONSTANT TIME
* But what if we have a function like the following
*/
const boxes = [0,1,2,3,4,5];
export default function logFirstTwoBoxes(boxes) {
console.log(boxes[0]); // O(1)
console.log(boxes[1]); // O(1)
}
logFirstTwoBoxes(boxes): // O(2)
/*
* Eeach time the function runs we have two operations so in total this function
* runs a total of O(2) every time, no matter how big the boxes get, the
* number of operations are the same, a flat line.
* When comes to constant time we don't care about O(1), or O(2). We call it
* simply as O(1)
* and o(1) => CONSTANT TIME
* Flat line in the graph.
*/
function funChallenge(input) {
let a = 10; // O(1)
a = 50 + 3; // O(1)
for (let i = 0; i < input.length; i++) { // O(n)
anotherFunction(); // O(n)
let stranger = true; // O(n)
a++; // O(n)
}
return a; // O(1)
}
/*
* 3 + n + n + n + n => O(3 + 4n)
* BIG O(3 + 4n)
* BIG O(n) => Simplified
*/
function anotherFunction() {
setTimeOut(()=> {
console.log('Another Function')
}, 1000);
}
funChallenge()
// Another challenge
function anotherFunChallenge(input) {
let a = 5; // O(1)
let b = 10; // O(1)
let c = 50; // O(1)
for (let i = 0; i < input; i++) { // O(n)
let x = i + 1; // O(n)
let y = i + 2; // O(n)
let z = i + 3; // O(n)
}
for (let j = 0;j < input; j++) { // O(n)
let p = j * 2; // O(n)
let q = j * 2; // O(n)
}
let whoAmI = "I don't know"; // O(1)
}
// BIG O(4 + 8n) => O(n)
/*
Rule 1: Worst case
Rule 2: Remove Constants
Rule 3: Different terms for inputs
Rule 4: Drop Non Dominants
*/
/*
Rule 1: Worst case
Example like the findNemo function, where we loop through the entire
array to find the element called nemo.
The function runs as many times as the quantity of elements in the input
so we can make the function more efficient calling a break;
*/
/*
Rule 2: Remove Constants
*/
function printFirstItemThenFirstHalfThenSayHi100Times(items) {
console.log(items[0]);
var middleIndex = Math.floor(items.length / 2);
var index = 0;
while (index < middleIndex) {
console.log(items[index]);
index++;
}
for (let i = 0; i < 100; i++) {
console.log('hi')
}
}
// O(1 + n/2 + 100); but we dropt the constants
// O(n + 1); but we dropt the constants
// O(n);
/*
Rule 3: Different Terms for Inputs
*/
function compressTwice(boxes, boxes2) {
boxes.forEach(function(boxes) {
console.log(boxes);
});
boxes2.forEach(function(boxes) {
console.log(boxes);
});
}
// O(2n) => O(n)
// now we have two inputs, one can be 100, and the other even more.
// so the loops deoend on the inputs
// BIG O O(a + b);
// If the arrays are nested then it should be O(a*b)
// What happened if the loops are nested
// Log all pairs of arrays
const array = ['a', 'b', 'c', 'd', 'e'];
function logAllPairsOfArray(array) {
for (let i = 0;i< array.length; i++) {
for(let j = 0; j < array.length; j++) {
console.log(i, j)
}
}
}
/*
When we see loops that are nested we use multiplication.
O(n) * O(n) => O(n * n) => O(n^2)
O(n2) -> Quadratic Time. Means every tiem the number of elements increase,
let's say we have 4 operations to do, if we have 3 elements to the
power of 2, and we can see that in the graph, the line bent and it
increases quite fast.
*/
/*
Rule 4: Drop Non Dominants
*/
function printAllNumbersThenAllPairsSums(numbers) {
console.log('these are the numbers');
nombers.forEach(function(number){
console.log(number)
});
console.log('and this is their sum');
numbers.forEach(function(firstNumber) {
numbers.forEach(function(secondNumber) {
console.log(firstNumber + secondNumber);
});
});
}
// tbe notations would be O(n + n^2) => as the rule says we drop the dominant
// part and becomse O(n^2)
