Big O notations and algorithms
In this post we're going to take a look at time complexity algorithms, for further details on the space complexity theme, there are additional resources at the end of the post
If you are a common person like me, you probably have a routine to your day, steps that you follow every day. Some people like to wake up and have a cup of coffee, and others brush their teeth first thing in the morning, and then have breakfast, go to the gym, take a shower, and so on. So, what this has to do with algorithms or Big O notations? Well, nothing with Big O for now, but, algorithms are like our routines, a set of instructions, talking about computer routines, when you open Twitter, for example, they have an algorithm to search for trends and the hottest tweets, or when you search for something on Google, they have a set of instructions to handle your input.
What problem do they solve
They are part of our day and do not necessarily "solve" a problem, but we can get what we want. We can search for an email by using a search algorithm, we can find one person on Instagram by their name, or we can do important things like landing a rocket on the moon. We use them to do heavy stuff that computers are pretty fast doing.
What makes a good algorithm
First, we need to think about what's a good solution for you, correctness? speed? Usually, we tend to prefer
both when talking about algorithm efficiency, but specifically speed, we can measure it through the Big O(n). And
before you thought that we have chronometers pointing to the computers running different algorithms, this is a stupid
way to measure them, because there are so many factors like processor speed, compiler optimization, or how the programming
language was built. Instead, we have Big O(n), which measures the speed of the algorithm according to the size of the
input assessing its worst-case scenario.
How the input size affects performance
It's undeniable that searching through a 500k thousand list of people's names from Facebook is heavier than a 2k discord members list. But how specifically, this affects the algorithm? Well, depending on your approach, or the algorithm type chosen, the algorithm can lose a lot of time searching through names that aren't important for the search, if you press T (20th letter of the alphabet) for example, the person that you are trying to find is much more likely to be next to the end of the list than to the start and comparing the linear and binary search approaches, we can confidently say that the binary search is much faster than the linear one.
Taking as an example an alphabetically ordered list of 500k names and utilizing the linear search algorithm O(n), if
our target is the last name of the list (worst-case scenario), we would need to go through 499,999 items to get to
our target. For example, if it was 1ms for each name that we would go through, the algorithms would take about 8 minutes
to complete the search, and if we would use binary search O(log n), the algorithm would take a 19 maximum of tries resulting in 19ms
How can I define the Big O of my algorithm?
Well, we have many articles and cheatsheets explaining the performance of each algorithm, but as I have said in the previous
paragraph, the speed of your algorithm is related to its input size, and the n inside the parenthesis of the Big O(n), is the
equation of your algorithm. So in a simple way of explaining, the n is the input size multiplied by the time that each process
would take, but we transform it into an expression: time * n. In the binary search for example, the
Big O is log n, equation explained by the following Stack Overflow answer
O(log N) basically means time goes up linearly while the n goes up exponentially.
What if I have more than one type of algorithm?
As said earlier, Big o takes the worst-case scenario. If Facebook used different algorithm types based on the user "membership", the linear algorithm for free users, and the binary search for premium users, the worst-case scenario is the linear search because it's the slowest. Check the code below.
_6switch (userType) {_6 case 'PREMIUM':_6 return binarySearchAlgorithm // O(log n)_6 default:_6 return linearSearchAlgorithm // O(n)_6}