Managing Big O Notation

In this blog I go over some concepts of Big O Notation that I've been breaking through after some months of practicing algorithms and might be helpful to others in the same process of improving their technical interview skills.

Time complexity

Tracks how long an algorithm takes to run (processing). We focus on time complexity when we really want to improve the performance of algorithms. Loops, recursion, and methods of iteration will usually increase the time complexity of algorithms and slow down our programs. Processing power is an expensive resource, and everyone needs websites to load fast so time complexity is has the higher priority when dealing with Big O.

Space complexity

It tracks the memory taken by the assignment of variables (RAM) and data types like integers, strings, arrays etc. Integers take a constant amount of memory O(1), but strings and arrays take more memory as they increase in size (n) O(n). However, space complexity is not a priority in the improvement of Big O notation in algorithms as RAM resources run out less frequently.

Nested Loops

Dealing with nested loops is a bit of a contradiction because most algorithms have a 'brute force' or 'intuitive solution' that uses nested loops. However every time we nest a loop the time complexity increases exponentially.

For example:

Code in sandbox

const countDuplicatesSlow = (numbers) => { // O(n^2) big o complexity

    let result = []

    for(let i = 0; i<numbers.length;  i++){ 

        let count = 0

        for(let j = 0; j<numbers.length;  j++){

            if(numbers[i] === numbers[j]){ // if we find a duplicate as we compare all numbers to all numbers

                count++

            }
        }
        result.push(`Found a total of: (${count}) number ${numbers[i]}s`)
    }

    console.log([...new Set(result)]) // print only unique for readability
}

Source: Aaron Martin (AJMANNTECH)

In this example, we use a nested loop to evaluate every item (outer for loop) against the rest of the items (inner for loop) and start to count how many duplicates we have on the array.

const duplicateNumbers = [1,2,3,2,1,2]
countDuplicatesSlow(duplicateNumbers)
// returns => [Found a total of: (2) number 1s,
//             Found a total of: (3) number 2s,
//             Found a total of: (1) number 3s]

This is a great example of an opportunity to improve Big O with a 'memoization' object. With this technique we can go from O(n^2) to O(n) which is a great improvement. I will be focusing on this in an upcoming blog.

Recursion

With recursion, the algorithms get very slow when we have to perform binary tree searches. Usually, if we search a binary tree
on all nodes the time complexity will be O(2^n) where n is the depth of the tree.

If we look at a recursion example like this adaptation from climbing steps on leetcode, which asks to find how many unique ways there are to go up a set of steps, when we can take either one or two steps on each opportunity to go up. The resulting time complexity is a O(2^n) which is even slower than an O(n^2) nested loop.

Code in sandbox

const recursionTreeSlow = (maxLevel) => {
    return recursion_Tree_Slow(0, maxLevel)
}

const recursion_Tree_Slow = (currentLevel, maxLevel) => {
    if(currentLevel > maxLevel){
        return 0
    }
    if(currentLevel === maxLevel){
        return 1
    }
    return recursion_Tree_Slow(currentLevel+1, maxLevel) + recursion_Tree_Slow(currentLevel+2, maxLevel)
}

In this slower recursion example the program unnecessarily builds the data multiple times on nodes that are the same. So the program is rebuilding data that has already been created but had not been stored, thus wasting resources.

The 'memoization' technique can also be used in binary tree recursion but understanding the implementation might need a bit more visualization because binary trees can be a bit more abstract than arrays and objects. I will also give it a go at explaining this in an upcoming blog.

Feel more than welcome to reach out and also to help with any comments/ideas.

LinkedIn
Twitter

Resources:

Big O Cheatsheet
Big O tips
Learn.co on time-complexity
AJMANNTECH
KodingKevin on Space Complexity