Big O Notation
In my field of software engineering there is this concept of Big O. This concept was not completely explained to me until I researched what it meant and why it was so important. According to Gayle Laakmann McDowell in Cracking the Coding Interview;
Big O is the language and metric used to describe the efficiency of algorithms.
Basically what this means is, it is a way to calculate how fast the program is going to run. It is crucial to know Big O and how to use it effectively because it can define how well your application scales. For example, you have a project that relies on grabbing specific information from your database. Let us say this information is profiles of users and you put it in an array. Putting this information in an array is okay, but then you try to sort through this information using loops within each other. The application may be fast enough to run with ten to fifty people, but what if your application grows to thousands of people? All of the sudden your application is slow because it is taking longer to loop through that huge array of data. Big O is supposed to solve this problem. There are many different runtimes for Big O. In this article I am going to talk about the most popular runtimes, what they mean, and give and example of some of the more complex ones.
O(log N)
O(log N) means you are going to divide your search into halves and look through each half to rule it out or if it is true. This is also known as a binary search, which is only effective in a sorted array. O(log N) is actually one of the most consistent, and fastest runtimes in Big O Notation.
Here is an example of a binary search I have done in Javascript:
In this example I did a binary search recursively to get the answer. This is O(log n) because no matter how big the data is, the time that it will take to run will not grow exponentially.
O(1)
O(1) means that the runtime of your function is constant no matter how big the file size, or array is (shown in example 1). Here is a quick example of what that looks like in Javascript:
No matter how big the array is, the function will always run the same.
O(N)
O(N) calculates the runtime based on how big the size of the array or file is. Instead of the time moving logarithmically, it is moving linearly.
Here is an example of what O(N) would look like in Javascript:
As the array gets bigger here, the longer it will take to filter through it. This is still an okay way to be able to calculate Big O and will scale pretty well.
O(n log n)
This kind of Big O Notation is usually performed recursively without a binary search, which makes it slower than just O(log n).
O(n²)
In this last part of my article I am going to talk about a bad practice in Big O, which is O(n²). People usually do this by having a loop within another loop. This is bad practice because it doubles your time to run the function.
Here is an example of what that looks like in Javascript:
Conclusion
Big O is crucial to know in programming to completely optimize your application. If your application cannot scale well, then people will probably stop using it for something else. I used to just write my functions and methods without really thinking about how well they can perform, as long as they worked. Do not make the same mistakes I have made and save yourself time in the future by making sure your application can scale now.
