Big O notation
Big o notation is a mathematical way to describe how any function grows depending on the input it receives. This information is very important to a web developer. It is very important if you want to understand how to build and work on scalable web applications. It is easy to run small web apps that only a couple of people use. In this case Big O notation is not too important as when n is so small it's more important to have a web app that is up and running and being used than to have it be optimized. The difference between an optimized and unoptimized algorithm at this small level will be miliseconds, almost unnoticeable to a user. The issue comes in when your web app becomes popular or you work at a large company with lots of data. Then the difference between using a O(n) algorithm and an O(2^n) algorithm is huge and could have dire consequences.
An example of an O(n^2) function:
// loop through the matrix and work out how many mines each cell is touching
for (let i = 0; i < gameArray.length; i++) {
for (let j = 0; j < gameArray[i].length; j++) {
// Inside here we would check out whether each of the neighbours was a bomb
}
}
The example above is an example I encountered while building the minesweeper game. This is a great example of an
O(n^2) if it is a square grid you are playing on in minesweeper or an example of O(m*n) if the minesweeper grid is
rectangle. Lets assume its a square one where gameArray.length === n, and gameArray[i].length === n.
For a 10 x 10 mine grid the outer loop would be executed 10 times and the inner loop 10 times for each of the 10
times of execution in the outer loop. Thus if we printed 'HI' inside the inner loop it would display 100 times.
The reason this is O(n^2) is the algorithm's performance is directly related to the square of the value of n.
If we increased n to 100, for example, we would print 'HI' 10 000 times compared to 100. So an increase by 10 on the
value of n resulted in an increase of 100 times the output, i.e. n^2
Linear searching is a search that finds elements by searching through the list in order until the element is found. Binary search is more like what you would do if you were using the yellow pages. You look halfway through and see whether the thing you are looking for is in the first half or the second half. In a binary search you would do this recursively until the element was found.
For binary search you would need the list to be sorted to be able to use the method. A linear search in big O notation could be represented as O(n), the binary search can be shown as O(log n). This is because after each iteration of the binary search the dataset n is effectively halved for the next iteration. This results in a curve that increases with n in the beginning but flattens out very quickly.
The fibonacci sequence is basically a series of numbers where the next number in the sequence depends on the two numbers that come before it in the sequence. To calculate the next number you add up the two numbers in the sequence that came before it. An example of a non recursive algorithm which works out a fibonacci sequence up to a given number. The big O notation for this example would be O(n) as when n increases the loop which works out the next fibonacci number and pushes it to the array will have to execute n times
// fibonacci function that isn't recursive
function myFibonacci(n) {
let fibonacciArray = [];
// push the first two numbers into the array as they will always be 1
fibonacciArray.push(1, 1);
while (fibonacciArray.length < n) {
// get the two numbers at the end of the array that need to be added
let int1 = fibonacciArray[fibonacciArray.length - 1];
let int2 = fibonacciArray[fibonacciArray.length - 2];
let newNum = int1 + int2;
fibonacciArray.push(newNum);
}
// log out the first n fibonacci numbers
console.log(fibonacciArray);
}
myFibonacci(50);
An example of a recursive function which can be used to calculate a list of fibonacci numbers
The big O notation of the below recursive solution to fibonacci would be O(2^n). I would not suggest using this
algorithm to find the first 500 fibonacci numbers. The time to calculate would increase exponentially.
function fibonacci(num) {
if (num <= 1) return 1;
return fibonacci(num - 1) + fibonacci(num - 2);
}
let fibonacciArray = [];
for (let i = 0; i < 10; i++) {
fibonacciArray.push(fibonacci(i));
}
console.log(fibonacciArray);