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:
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.
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.
Resources:
Big O Cheatsheet
Big O tips
Learn.co on time-complexity
AJMANNTECH
KodingKevin on Space Complexity
Top comments (0)