Big O notation basics for Web Developer

Big O notation basics for Web Developer

Big O notation is a way to describe the speed of an algorithm. Big O notation tells you the number of operations an algorithm will make. It gets its name from the literal "Big O" in front of the estimated number of operations and As a web developer we will deal with algorithm and operations in our work now and then and it is important to make sure the logic or algorithm you decide to use for a particular situation is the best decision.

What is quadratic function (O(n2​ ​)) ?

O(n²) means that the calculation runs in quadratic time, which is the squared size of the input data, O(n^2) means that for every insert, it takes n*n operations E.g if the size of input (length of list) triples, the processing time (roughly) triples. And if it increases hundredfold, the processing time also increases in the same magnitude.

O(n^2) algorithms become inefficient for handling large number of items

The best example of this is nested loop and below is an example


for (num = 1; num < 50; num++) {
 for (numTwo = 1; numTwo < 50; numTwo++){
 }
}

Linear usually refers to something that follows an expected order or sequence so A linear search scans one item at a time, without jumping to any item, the time taken for linear search gets bigger at the same rate as the data does, While Binary (or base-2) a numeric system that only uses two digits — 0 and 1. Computers operate in binary, meaning they store data and perform calculations using only zeros and ones so a Binary , binary search cut down your search to half as soon as you find middle of a sorted list.

Binary search is better than Linear search because of the amount of time is takes to perform the search

Compare a linear search with a binary search algorithm

  • Linear Search has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.

Code Example

function linearSearch(arr, key){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === key){
            return i
        }
    }
    return -1
}
  • The time complexity of Binary Search is: O(log n) [ Logarithmic ], which is a very good time complexity

Code Example

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);

        if (sortedArray[middle] === key) {
            // found the key
            return middle;
        } else if (sortedArray[middle] < key) {
            // continue searching to the right
            start = middle + 1;
        } else {
            // search searching to the left
            end = middle - 1;
        }
    }
    // key wasn't found
    return -1;
}

We used two variables to keep track of the start and end of the current subarray we are searching. We find the middle element, and then check whether it is equal, lesser than, or greater than the key

What is Fibonacci sequence ?

The Fibonacci sequence is a series of numbers where a number is the addition of the last two numbers, starting with 0, and 1

   The Fibonacci Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Different Algorithm to display first 5 sequence of Fibonacci Sequence

Program to display fibonacci sequence using recursion

function fibonacci(num) {
  if (num < 2) {
    return num;
  } else {
    return fibonacci(num - 1) + fibonacci(num - 2);
  }
}

if (5 <= 0) {
  console.log("Enter a positive integer.");
} else {
  for (let i = 0; i < 6; i++) {
    console.log(fibonacci(i));
  }
}

Javascript program to write the first 5 numbers in the Fibonacci sequence using Loop

let n1 = 0;
let n2 = 1;
nextTerm;

for (let i = 1; i <= 5; i++) {
  console.log(n1);
  nextTerm = n1 + n2;
  n1 = n2;
  n2 = nextTerm;
}

Loop ends at the end of the sequence it is looping over. However, a recursive function could continue indefinitely since it doesn't necessarily have a sequence of data. so loop is better algorithm .