Big O Notation for beginners!!

Why beginners should not be afraid of AL

As a code newbie, I have read a few posts that say algorithms are not useful if you want to be a front-end dev or as a beginner in web development in general. For sometime, I brushed it off saying it was a difficult topic, only for advanced engineers and beginners "should not try it". The thing is, learning AL helps you write better code and easily identify what is slowing down your program.

I spent a few days learning it and I can say, as long as you have the syntax and fundamentals down of any programming language, you can start learning algorithms. You don't have to be programming for x years, you can learn as you go by. The early you start, the better and no you don't have to be a genius in maths.

So to all my code newbies don't be afraid to learn, go for it and when you fail, try it again. You can't be good at something if you have never tried. As for me, I have failed and solved some of the questions I went through but I have learnt from them and I keep on growing.My problem solving skills keep becoming stronger 💪🏾. Yes we are all learners, in this field you will never stop learning.

What is an algorithm?

This are steps taken to solve a problem. We are identifying patterns, creating a solution that will improve the speed of our programs.Increasing Performance matters a lot in algorithm not just writing code that works.

What is big O notation

Big O notation is used to explain the performance or complexity of an algorithm.
we can also say, It shows how the runtime of the algorithm grows as the input grow. Example if you are in a large company that deals with a lot of user data, writing an efficient algorithm that takes less time when it runs compared to one that's takes more time.

Why is big O notation is important

• It helps us look at the worst case scenario of an algorithm.
• Describes the time execution which is called Time complexity
• Describes the space used (memory). This is called Space complexity.

Common Time complexities

1) O(n) - Linear runtime

As the input of a function increases the runtime also increases.
Let's look at the example below.

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

In the above function, we don't care as much if the input(n) is 5 or 1000. We want the order of magnitude( big O)which will be O(n)- ( f(n) = n ). As the input size increases the time it takes for the loop to run also increases.

2) O(n^2) Quadrantic runtime

The runtime is directly proportional to the square of the input(n^2). Hence as the input grows, the runtime grows n * n .
To understand it better, let's look at the example below.

const pairs = (n)=> {
    for (var i = 0; i < n; i++) {
      for (var j = 0; j < n; j++) {
        console.log(i, j);
      }
    }
}
pairs(2);
/*
output
0 0 
0 1
1 0 
1 1
*/

The function above has a nested loop. When n grows the number of times the loop runs increases in the first loop and the number of times the second loop runs also increases. This is = ( f(n) = n ^ 2 )

O(1) Constant runtime

As the input of a function increases the runtime doesn't change it remains constant.
Let's take a look at the example below.

function logAtMost10(n) {
    for (var i = 1; i <= Math.min(n, 10); i++) {
        console.log(i);
    }
}

In the function above when the input is more than 10, it returns 1-10. Even when the input is 1M, the output will still be 1-10. As n increases the runtime to the function remains the same, ( f(n) = 1 ).

In big O notation the smaller terms are not important. Example:

O(n + 50) => O(n) '

If you remove the 50 it will be O(n)

O(8000n + 50) => O(n)

O(n^2 + 10n + 3) => O(n * n)/ O(n2)

On a larger scale 5n + 6 is not important but n^2 is.

O(n^2 + n^3) => O(n^3)

A few things to note

Arithmetic operations(+, -, /, *) are constant.

If you add, subtract or multiple, it takes the same amount of runtime, hence been constant.
When you do 1 + 1 and 3 + 1000000000 in your computer, it roughly takes the same amount of time to do the operations.

Assigning variable is constant.

Assigning variable x to 10, takes the same amount of time as assigning variable y to 1,000,000.

Auxiliary Space

Auxiliary space is the amount of memory or space needed to run the algorithm. But with space complexity, the total amount of space needed, grows as the input size increases.

Let's take a look at some few examples.

Question 1

//O(1)
const total= (n) => {
    let total = 0;
    for (let i = 0; i < n.length; i++) {
        total += n[i];
    }
    return total;
}

O(1) space - this means the space is the same no matter the input. Therefore the input increasing or decreasing doesn't affect the space.

Question 2

const double = (n) => {
    let total = [];
    for(let i = 0; i < n.length; i++) {
        total.push(2 * n[i]);
    }
    return total; // return n numbers
    //O(n) space
}

In the function above, if the input has 10 items, the new array created will have 10 items that are doubled. The space needed will be O(n)

A simple table for all the runtime complexities

Questions to practice with.

What is the time complexity and Auxiliary space of the following questions
Question 1

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

Question 2

function onlyElementsAtEvenIndex(array) {
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++) {
        if (i % 2 === 0) {
            newArray[i / 2] = array[i];
        }
    }
    return newArray;

}

Question 3

function logAtMost10(n) {
    for (var i = 1; i <= Math.max(n, 10); i++) {
        console.log(i);
    }
}

Conclusion
This is what I have learnt so far and I hope it helps. As I continue learning algorithms I will be posting.
I am grateful you have read all the through.

A few resources

• Practical guide to algorithms in Javascript by frontend masters
• Algorithms by YK Sugishita (CS Dojo) Youtube channel
• A beginner's guide to Big O notation

You can also support me, if this article helped you. 🙂