Big-O notation basics for web developers

 Big O Notation...the eye stretcher at first glance👀🙈🙉🙊💣💢💀

BIG O => Order Of Magnitude...

Confused about Big 0 Notation? Well it looks all intimidating at first but luckily as a entry-level Web Developer, it is important to understand that Big O notation is used to describe and analyze the performance of code so don't get too freaked out my the mathematics of it for now.

Let's dive straight into the definition of Big O notation:

Big O notation is a mathematical function used in computer science to describe the performance or complexity of algorithms.

It can describe things like the execution time required or the space used by the algorithms..

Why is it important for Web Developers to understand Big O notation? 

It is a fundamental tool as we now know, to analyze the time and space of algorithms. This becomes very useful to Web Dev's when starting to write software for millions of users because it will allow you to analyze the efficiency of different algorithms. This will help you as a Web Developer to build a well designed and thought out Web application. This could potentially help your application to scale and perform better than competitors.

There are many types of big O complexities used but we'll discuss some of the more common types of Big O complexities that are used, let's take a closer look at these:

1) O(1) - Used to measure constant time complexity

* Regardless of the input size, the algorithm will always maintain a constant runtime.

A code example of this would be as follows:

function constantFunc(n) {
    return n*n;
}
// 'n' multiply itself...

The input size will not effect the time to run the algorithm and it remains constant throughout.

2) O(log n)-  Logarithmic time complexity


* The time climbs linearly while the 'n' goes up exponentially. For example, it will take roughly one second for execute 10 elements and about 2 seconds to execute 100 elements.

Example code of this:

function log(n) {
    for (let i = 1; i < n; i*=2) {
        const result = i;
        console.log(result);  
    }
}

The number of iterations will always be less than the log of the input size.

3) O(n)- Linear time complexity

* This will will happen when an algorithm's performance grows in line with the size of the input data.

Code example:

function linearFunc(n) {
    for (var i = 0 ; i < n; i++ ) {
        console.log(i)
    }
}

Constant time operations will run in a basic for loop function.

Difference between Linear & The Logarithmic search:

Linear search algorithm- Each element of an array is searched one by one in logical order to see if it is the desired element. Depending on where the desired element is in the array will detemine the time complexity of the algorithm. It is easy to use and it has no need for ordered elements, it also requires less lines of code.

compared to Logarithmic or Binary search algorithm- The binary search algorithm is faster in finded the desired comparison within the array due to it's order system. A very complex algorithm where elements have to be in a specific order and require more lines of code.

The binary search algorithm will be the most efficient algorithm between the two as it takes less time to search through the sorted list of elements because it's prerequisite is that all elements need to be sorted in order whereas the linear algorithm has no such requirement.


4) O(n2) Quadratic time complexity

This complexity is exactly as the name states, it takes a tremendous amount of time to run the algorithm based on the data input set.   

* The time the algorithm will take to run will increase greatly as the size of the input data set increases.

Example code:

// nested for Loop:
for (int i = 0; i <n; i += c) {
    for (int j = 0; j < n; j += c) {
    // some O(1) expressions
    }
}

The good example of Quadratic time complexity functions would be that of  nested loops. The size of the input data set will dramatically affect the run time of the algorithm as shown in the diagram above. The inner loop runs "n" times and isn't dependant on the value of  n hence the algorithm's time complexity. The time complexity will take place when we nest over multiple iterations within the data set.

Next we'll discuss the fibonacci Sequence:

What is the Fibonacci Sequence?
In simple terms, it is a series of numbers where each digit is the sum of it's previous two neighbors.An example of what this series looks like is as follows: 1, 1, 2, 3, 5, 8, etc.

I'm going to compare the difference between a recursive function used to get the Fibonacci Sequence and a non-recursive function:

My code for both is as follows:

Recursive Function used-

/*
 JavaScript program that will display the fibonacci sequence
 between 1 & 5 using a recursive function.
The recursive function calls itself within its declaration.
*/
function fibonacci(num) {
    if (num < 2) {
        return num;
        //console.log(num); // Log output 0;
    }
    else {
        return fibonacci(num - 1) + fibonacci(num - 2);
    }
}

// Take in a term between 1 & 5:
let Terms = prompt('Enter the number of terms between 1 & 5: ');
// Allow user input.
// Prevent term less than 1:
if (Terms <= 0) {
    document.write('Enter a integer between 1 and 5, not less than 1...');
}
// Prevent term greater than 5:
else if (Terms >= 6) {
    document.write('Enter a integer between 1 and 5, not greater than 5...')
}
// Display fibonacci sequence...
else {
    for (let i = 0; i < Terms; i++) {
        // console.log(fibonacci(i));// Log fibonacci sequence.
        document.write(fibonacci(i))
    }
}

// Fibonacci sequence output : 01123...

Non-recursive Function used-

/*
 JavaScript program that will display the fibonacci sequence
 between 1 & 5 using a non-recursive function.
 */
function fibonacci(num) {
    let a = 0, b = 1, f = 1;
    for (let i = 2; i <= num; i++) {
        f = a + b;
        a = b;
        b = f;
    }
    return f;
};

// Take in a term between 1 & 5 via prompt:
let Terms = prompt('Enter the number of terms between 1 & 5: ');
// Allow user input.
// Prevent term less than 1:
if (Terms <= 0) {
    document.write('Enter a integer between 1 and 5, not less than 1...');
}
// Prevent term greater than 5:
else if (Terms >= 6) {
    document.write('Enter a integer between 1 and 5, not greater than 5...')
}
// Display fibonacci sequence...
else {
    for (let i = 0; i < Terms; i++) {
        // console.log(fibonacci(i));// Log fibonacci sequence.
        document.write(fibonacci(i))
    }
}

// Fibonacci sequence output : 11123...

An efficiency test was done between the two algorithm examples above and the result was that:

The iterative example being the non-recursive example above, I found was a lot more efficient in fetching and returning the items opposed to the non-recursiv function used which lacked efficiency in finding and returning the desired items.

The recursion seems to consume more memory as it fills up the stack and took significantly longer to achieve the same goal.

The End...until next time!😉


Comments

Post a Comment

Popular Posts