Big O Notation

To measure the performance of the code, we use something called Big O notation. It is used for determining time and space complexity of the code. We have 4 rules when it comes to determining Big O Notation:

1. Always use the worst case: Even if best case results in O(1), if the worst case is O(n), the algorithm is still at O(n).
2. Drop the constants: If we have O(1/2n + 1), we drop the constants and turn it into O(n)
3. Drop the non dominant: If we have O(n! + n^2 + 99n), big O is O(n!)
4. Different terms for different inputs: If we have 2 different inputs passed as an argument to the function, we use 2 different terms to represent their complexity (ie. O(m) and O(n)). So if we have 2 loops that depends on each input, we would have O(m + n) instead of O(2n).

# References

• Master the Coding Interview