Big-O Notation
One of the most important goals when working on very large applications, is to make sure that it’s performant and scalable. In Computer Science, we leverage the Big-O notation to calculate the Time & Space complexity of our code.
Thus far, this is the best leading and proven logic you can leverage to see how fast your algorithm is and the amount of memory space it’s using. Knowing the correct algorithm to use in your application, depending on the use case, will ensure your application is performant and scalable given the number of input data.
Simply put, Big-O notation gives us a rough estimate and indication of the worst-case scenario an algorithm will perform when the input data grows over time.
For example: the following notation:
- Time Complexity = O(n^2)
- Space Complexity = O(n)
Indicates that the algorithm will perform slower, and it will require more memory as n (the number of data items) gets larger. If we were parsing a csv file that had 1,000 lines, then n = 1000.
There’s a mathematical analysis used to calculate the Big-O of a given algorithm, which I will go into detail later. In most cases, we don’t need the math to figure out the Big-O of a given algorithm. The simplest case to remember is, if your code is using a single loop that iterates through all your input data n only once, then the Big-O of your algorithm is O(n). Whenever you have written Nested Loops: 2 Loops = O(n^2) (read as Big-O of n square), 3 Loops = O(n^3), 4 Loops = O(n^4), etc…
It is important to remember that the Big-O calculation is crucially important when working with large input data. The following is a good example that will test this theory.
When it comes to implementing a Sorting Algorithm: Insertion Sort = O(n^2), Merge Sort = O(n log n), in theory we can see that Insertion Sort will perform slower when the input data is larger compare to the Merge Sort. But if your input data is smaller, and your array was somewhat sorted, the Insertion Sort = O(n^2) will perform faster.
For now, please refer to the following Table below to quickly grasp the Big-O Notation:
Time Complexity vs Space Complexity
