This blog gives a short summary on Big O Notation, specifically for technical interviews.
What is Big O Notation?
The "O" in Big O Notation (that's "O'" the letter, not a zero) comes from the German word "Ordnung" which means the order of approximation. Big O is used to estimate the performance of code based on its time and space complexity. It's a way to compare performance and runtime in the event inputs were to grow indefinitely - or, to the biggest number you can think of.
Big O Results
The ideal solution will have the smallest, or less steep, Big O as possible. The most common Big O results are:
- Constant, O(1) - operations, un-ordered data structures like object manipulation, variable assignments, inserting/deleting at the end of an ordered data structure
- Linear, O(n) - loops & iterations, anytime you need to search or step through an ordered data structured, inserting/deleting at beginning of an ordered data structure
- Log, O(log n) - recursion functions, searching algorithms
- Quadratic, O(n^2) - nested loops & iterations
Calculating Big O
To calculate Big O, count the number of operations in your code snippet and count as many times as the code runs. This means that if you are looping (or iterating), the code would perform the operation n amount of times. If you use a nested loop, this means the operation runs n * n number of times - so this would be quadratic O(n^2). If you add a number then multiply it by something, you are performing 2 mathematical operations and hence would be a constant O(2).
Simplifying Big O
Big O should be simplified to its lowest form. For example, if your code has 5 mathematical operations and involves an 2 iterations, this can be simplified to O(5 + 2n) -> O(n). The idea behind this is that a huge number will still be a huge number if multiplied by 2 and added 5.
A Trick to Reduce Big O with Arrays
When dealing with manipulating arrays, order matters. If you add (.unshift) or remove (.shift) to the beginning of an array, you are shifting every item in the array and hence every item needs to be re-indexed. This creates a linear Big O, O(n). Instead, add (.push) or remove (.pop) from the end of the array, so that the other indexes in the array remain unchanged. This gives a more ideal Big O: constant O(1).
Top comments (0)