What is Big O notation and why you should know about it

 

What is Big O ?

The Big O notation also known as Landau's Symbol. The " O " stands for " order of magnitude ".  Order of magnitude refers to the rate of growth of a function. 

It is the language we use for talking about how long an algorithm takes to run or how much memory is used by an algorithm. 

It can be used or rather can express the best , average or worse case running time of an algorithm.

As stated above it would be obvious as to why developers would need to understand the concept of Big O notation as it analyses the cost of an algorithm and how fast it is.

    What is a quadratic function O(N2) ?

In mathematics , a quadratic polynomial is a polynomial of degree 2 in 1 or more variables. 

Now in technical jargon and much simpler terms it is the process of solving certain mathematical optimization problems involving quadratic functions.

Specifically , a dev would seek to optimize a multivariate quad function subject to linear constraints on variables.

Lets take a look at an example.

bool ContainsDuplicates(IList<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++) 
    {
        for (var inner = 0; inner < elements.Count; inner++) 
        { 
            // Don't compare with self 
            if (outer == inner) continue;             
            
            if (elements[outer] == elements[inner]) return true; 
        }
    }    
    return false;
}

The example above above represents the performance of an algorithm that is proportional to the square size of the size of the input data set. This is common as the deeper the nested iterations go the higher the root number will be.

Linear and Binary algorithm 

The linear search algorithm is used on a collection of items. It is dependent on the technique of traversing a list from beginning to end by exploring properties of all elements that are found on the way.

The binary search algorithm is a algorithm that finds the position of a target value within a sorted array , it compares the target value to the middle element of the array.

Below are 2 examples , the first is linear and second is binary.

1. arr = [42,2,3,1,4,6] search_n = 2 for position, item in enumerate(arr): if item == search_n: print("%d The searching number is at position %d inside the array."%(search_n,position+1)) break else: print("Sorry! Not Found.)
2. const arr = [1, 3, 5, 7, 8, 9]; const binarySearch = (arr, x , start=0, end=arr.length) => { // If the item does not exist, return -1 if(end < start) return -1; // Calculate middle index of the array let mid = Math.floor((start + end) / 2); // Is the middle a match? if(arr[mid] === x) return mid; // Is the middle less than x if(arr[mid] < x) return binarySearch(arr, x, mid+1, end); // Else the middle is more than x else return binarySearch(arr, x , start, mid-1); } binarySearch(arr, 7); Returns 3

There are similarities between these 2 algorithms but the only thing that really matters is which is more efficient for programmers to implement.

In terms of efficiency binary is much faster in terms of scan cycles and more efficient compared to linear search especially when larger data sets are involved

What is the fibonacci sequence ?

The Fibonacci sequence is a set of integers that start with a zero, followed by a one, then another one then by a series of steadily increasing numbers.

The sequence follows the rule that each number is equal to the sum of the preceding 2 numbers.

With the fibonacci sequence being created with recursion the max depth is proportional to the N , hence the space complexity of Fibonacci recursive is O(N).

You can store just the 2 previous values of the fibonacci number and not everyone since you only need the previous 2 to calculate the next one. The array method is superior to the recursive method since it takes less time and less memory to compute then the recursive one.

Below will be 2 examples , the first being with the recursive method and the second without.

// Recursion way to return Fibonacci numbers

function recursiveFibonacci(n){

 

    if(n === 0) return 0

    if(n === 1) return 1

 

    return recursiveFibonacci(n - 2) + recursiveFibonacci(n - 1);

}

console.log(recursiveFibonacci(4))

// n = amount of numbers in sequence will be displayed

function fibonacci( n ){

    const fib = [ 0 , 1 ]

    for( let i = 2; i < n ; i++ ){

        fib[i] = fib[i-1] + fib[i-2]

    }

    return fib

}

console.log(fibonacci(7))

console.log(fibonacci(2))

There are no wrong or right way of doing things especially in programming , the code above is responsible of doing the same thing but using different approaches.

Always try to find the most simply and efficient way of doing things.