Understanding The Big-O Notation In Its Simplest Form
Algorithms are essential to computer programming. Its embedded in all the languages we are learning and using. Sooner or later in your programming journey, you will come across the Big O Notation. It is one of the most talked about concepts/functions thats tied to algorithms. The Big O Notation is a mathematical function used to evaluate the complexity of an algorithm. The complexity of an algorithm under the Big O Notation is usually measured in time and space. Or rather how an algorithms run time or space requirement grows as the input increases.
Time complexity is used very often to evaluate the efficiency of algorithms. Amazon, one the highest trafficked sites has millions of users. As a user, you want to be able to login and browse within a few seconds barring any network outage. If an O(n) algorithm (linear time) was used to looped through the Amazon’s users database to validate and authenticate an account, you would probably leave the site and never come back.
The better solution to the problem is to be able to use a O(1)algorithm (constant time). This means, no matter the amount of input (whether its 1 million or 1 thousand) the time it takes to authenticate will be a constant number.
Big O’s 0(n²) is know as a quadratic algorithm. One of the most common ways you might see this algorithm is in a nested loop. In the example below, the method is asking to print out the numbers one through five a total of five times; resulting in 25 outputs.
You might also get a situation when you have two algorithms with different run times. This doesn’t necessary mean its O(2N) or O(n²). Often times, you have different inputs for these two algorithms. The example below shows two algorithms or functions within a the same function. As you can see, there is a nArray and a mArray. In this situation, the run time would be O(n) + O(m). If the inputs are different, you should differentiate using different variables. One key takeaway is that the variable doesn’t have to be n, it could anything as long it makes sense to the context.
The chart below is a simplified break down and ranking of the Big O algorithms from another post. If you want to learn it in simplified Ruby terms, I have provide a link below to that post.
