Algorithms and data structures

These are my notes for the algorithm course of frontend masters. This first page contains the introduction for the course, and the subsequent sections are listed below.

Big O

Big O is a generalized way to be able to understand how an algorithm will react as the input grows. It helps take decisions on which data structures and algorithms to use and how the programs will perform.

Basically: as your input grows, how fast does computation or memory grows?

Important concepts:

1. Growth is with respect to the input
2. Constants are dropped
3. Worst case is usually the way we measure

Growth is with respect to the input

Example:

function sum_char_codes(n: string): number {
    let sum = 0;
    for (let i = 0; i < n.length; ++i) {
        sum += n.charCodeAt(i);
    }
    return sum;
}

To tell how the program grows, the easiest way is to look for loops. This code counts the sum of characters in a string. For each new character added, a new loop has to be done. It means that it grows linearly. If there's 50% more characters, it will take 50% more time. It's called O(N).

Constants are dropped

So what happens when we add a new loop?

Example:

function sum_char_codes(n: string): number {
    let sum = 0;
    for (let i = 0; i < n.length; ++i) {
        sum += n.charCodeAt(i);
    }
    for (let i = 0; i < n.length; ++i) {
        sum += n.charCodeAt(i);
    }
    return sum;
}

In this example the loop happens twice, so the reflex would be to think it takes twice the time or O(2N). But it's not correct: the goal is to describe the growth of the algorithm, not how much time exactly it takes or how much CPU it will use. The number of times it is executed does not change it's growth.

So in this case, the correct notation would be O(2^N). This is why constants are dropped in Big O notation.

Example of why constants are not a good indicator, with N as the input:

N = 1, O(10N) = 10, O(N^2) = 1
N = 5, O(10N) = 50, O(N^2) = 25
N = 100, O(10N) = 1,000, O(N^2) = 10,000 // 10x bigger
N = 1000, O(10N) = 10,000, O(N^2) = 1,000,000 // 100x bigger
N = 10000, O(10N) = 100,000, O(N^2) = 100,000,000 // 1000x bigger

Consider the worst case

Example:

function sum_char_codes(n: string): number {
    let sum = 0;
    for (let i = 0; i < n.length; ++i) {
        const charCode = n.charCodeAt(i);
        // Capital E
        if (charCode === 69) {
            return sum;
        }
        sum += charCode;
    }
    return sum;
}

In this example, the sum is returned when E is encountered, so logically the growth could be O(n - x) where x is the number of characters skipped after E.

But since we don't know where E is located (it could be at the end, the start, the middle), we consider the worst case scenario, and it means that this growth is O(n), as if E was the last character of the string.

Complexity

Some algorithms are notoriously heavy in operations and are therefore not recommended, and their Big O notation helps to identify them, as per the graph below (source).

We already saw the O(2^N) before, here's the O(N^2):

function sum_char_codes(n: string): number {
    let sum = 0;
    for (let i = 0; i < n.length; ++i) {
        for (let j = 0; j < n.length; ++j) {
            sum += charCode;
        }
    }
    return sum;
}

Same with O(N^3):

function sum_char_codes(n: string): number {
    let sum = 0;
    for (let i = 0; i < n.length; ++i) {
        for (let j = 0; j < n.length; ++j) {
            for (let k = 0; k < n.length; ++k) {
                sum += charCode;
            }
        }
    }
    return sum;
}

Data structures

Examples of data structures

Search algorithms

Examples of search algorithms

Sorting algorithms

Examples of sorting algorithms

Arrays algorithms

Examples of Arrays related algorithms

Recursion

What is recursion? What is recursion? What is recursion? What...

Quicksort

An example of recursion sorting algorithm

Trees

Explanation of the tree data structure

Tree Search Algorithms

Examples of trees related algorithms