Well, simply put it is a measurement that is used in order to determine the time complexity of an algorithm, or in other words, how quickly it will take for this algorithm to complete its task.
I will be going over three Big O classifications, O(1), O(N), and O(logN), and try to explain them as best as I can.
Let’s start with the basics.
Say, for example, we write down a simple piece of code print "Hello world!" (yes the overdone hello world, I had to!) and I ask you “what type of algorithm would you describe this line as in terms of Big O ?” You might say “Um, that is a simple print and is not an algorithm.
” To which I would respond, “Well actually any line of code that is completing a task is an algorithm, but it is true that the complexity may be extremely low like in this case.
”That said, the line print "Hello World!" is what is known as, in Big O notation, O(1) which means very simply that the algorithm will take the same number of steps, no matter how much data there is, to complete (in this case one).
So, as another example, let us say we have an array of fruit fruits = [ "apples", "oranges", "peaches"] reading from this array will only take one step regardless of how long the array may be therefore this array will also be categorized in Big O as O(1).
Now that we understand O(1), let's try to think about searching an array for a specific value.
Given our fruits array mentioned above say we were only looking for an element(s) in that array that contains the letter “p”, simple enough, we would write a simple loop that would iterate through said array and display the elements that contain that letter.
With this in mind, we now can see that this type of algorithm would most likely not be O(1) since the number of steps it would take to complete this would depend on the size of the data set.
That size, in Big O, is referred to as “N” and if we were to classify this loop in terms of Big O notation it would be O(N), or it would take “N” times to complete this algorithm.
Before talking about the third classification I want to talk about binary search.
A great example I read on binary search goes like this.
Imagine you were playing a guessing game of higher and lower and you had to guess a number between 1 and 100 and I picked 75.
The best approach to this would be to first say 50, thereby eliminating half the results.
Next, you would say the halfway point between 50 and 100 which would be 75, you will have narrowed the search down in two steps!.Of course, I made it easier by picking a halfway point but the point still stands even if the number was 65 or 70, it would just take one or two more steps.
This is binary search, you are cutting the elements in half to get to the result faster.
Now, knowing what we already know about O(1) and O(N) this clearly does not fall into either of these categories.
This dataset would not take one hundred (N) steps to complete as O(N) might say, and definitely does not take one or seven or nine steps every time.
We would classify this type of algorithm as O(log N), which if we were to think about the guessing game example above, is essentially the number of steps it would take to halve data sets until there is only one remaining, and binary search falls directly in this category.
One stipulation, however, is that binary search will only work on an ordered array and cannot work for anything else.
Awesome!.You made it through the explanations.
Now let's visualize these concepts as a whole.
How would you rank these classifications in terms of time complexity?Have you got it?.Well, O(1) is definitely the fastest, as it will only take one step or the same amount of steps to complete depending on the complexity of the algorithm.
O(log N) is next as it can take a larger dataset and complete much quicker by halving each result.
Finally, you probably guessed it, O(N) is definitely the slowest since for every piece of data it will take one additional step to complete it.
Hopefully, this introductory explanation into Big O notation has helped on your path to being a better programmer, I can definitely say for me it has!.Cheers!.. More details