**bold text**
“A great challenge of life is knowing enough to think you are right, but not knowing enough to know you are wrong”. 

Neil deGrasse Tyson wrote.

This thinking was what caused my error in that previous post. I thought I knew the Big O so well that I didn't need to recheck my facts.

But Big O can be a little tricky to explain simply. Yet, I'll try again anyway. 

So, here goes the Big O notation.

Please keep in mind that this post does not give all the necessary information on the topic. There's more about it online.  

Here, I only seek to help:

Understand the Big O and why it's used 
Know how to determine the Big O notation for a piece of code by using a few examples.
So, What is the Big O Notation and Why is it Used?
The Big O notation is a means of communicating the runtime or performance of an algorithm.

Performance in this sense refers to how much time the algorithm takes to execute its instructions. 

It also indirectly means that some Big O notations are better than some; some perform faster than others.

Big O notations are used because programmers want to be able to communicate this "performance" of algorithms to other programmers. 

It is also used because programmers want to be able to compare algorithms and pick the best ones to use in their programs.

Consider the scenario that you are a software engineer in a big tech company and you write the code that is used to search users on this new platform that the company will soon be launching.

You go into a meeting on Monday morning and your CTO asks you how good is the search algorithm you wrote for the platform?

Without using the Big O notation, you might answer with this: "Well sir, with five users in the system, the algorithm takes 0.9 milliseconds to find a user. But with a thousand users, it takes 12 seconds".

Excellent reply.

But the problem with that response is that you don't know what the performance of the algorithm is for five hundred thousand users. 

You will only know it when the system goes live and a five hundred thousand users sign up, or when you simulate a five hundred thousand users - just like you might have done for the five users and the thousand users.

That's hard work to be done for every user number imaginable.

So instead of doing that, you reply with this instead: "well sir, it is an O(n) algorithm so it's really quite good".

With that, everybody who knows what O(n) algorithms are knows how good the algorithm is. 

But that does not mean that they can give you an exact time in milliseconds or seconds of how long it would take to find a user with a specific user number.

It means that they know that it compares the searched user with almost every user in the system until it finds the user. So with a large number of users it will take a lot of time to find the user.

So, for instance, if the users are in an Array, and the sought user is the last item in the Array, then the algorithm would compare with all the items in the Array until it gets to the user at the last slot.

If the user was in the middle instead, then once it finds the user in the middle, it will stop searching.

Now, after your reply, your CTO says: "well, i think i have a better solution that we should use instead. Mine takes 0.3 milliseconds with five users and with a thousand users, it takes 8 seconds". 

That's what he would say, too, without using Big O.

But with Big O, He/She says: "Well, I think I have a better solution that we should use instead. Mine is an O(logn) algorithm. It is faster than what we currently use".

Immediately, everyone knows this is probably what His algorithm would do.

Sort all the users into an ascending order based on the first character in their surname
e.g [Alan, Addo, Anton, Brad, Bellick, Boadu, Chadwick, Coffi, Kantanka, Kwarteng, Xavier]
Then it would divide them into two Arrays. Each containing names starting with a particular alphabet
A=[Alan, Addo, Anton, Brad, Bellick, Boadu]
B=[Chadwick, Coffi, Kantanka, Kwarteng, Xavier]
Then it searches for the user in the Array which has names that start with the same character as the sought for user
It repeats steps 1 and 2 repeatedly with each split array as a new users array until it finds Addo (if we are searching for Addo)
That may seem a bit difficult to understand for now, but you'll get it below...

But at this point, you'll now understand that unlike your algorithm that compares every item in the list, this algorithm divides the users array into two repeatedly until it ends up with the searched user. 

Therefore it would use half the time yours will take if there were only two users to search through. 

So, theoretically, assuming you had N amount of users to search through, then after the first iteration of steps 2-4 listed above, you'll have the below users to search through for your CTO’s proposed algorithm and for your algorithm.

O(logn)         O(n)

n/2                  n

Now after iteration 2, you'll have the below results. But remember that Addo will be searched in only one of two arrays that resulted after the division above. And that array will go through steps 2-4 again. So it would also be divided into two again. So the n/2 array which is searched is divided further to give

O(logn)         O(n)

n/4                  n

Next iteration

O(logn)         O(n)

n/8                  n

And it goes on and on until the user is found or the end of the Array is reached.

Without going on further with this scenario, I think you should get the point by now.

So Let's Sum it Up
Using the Big O notation, we are able to directly communicate the speed, runtime or performance of algorithms and are also able to compare them without actually testing the algorithms with wild amounts of input data (which in the scenario above is the users).

Without using Big O notation to describe algorithms, the performance of algorithms would only be known by testing them with inputs depicting particular test cases, say a thousand users, five-hundred users or a million users.

That’s wild!

It also means that without testing for a particular test case, algorithms cannot be ranked on performance for that test case. 

That is why the Big O notation is used.

The scenario I have used to explain the Big O notation in this post is known as Time Complexity of Algorithms. But the Big O notation is also used to describe algorithms based on their space usage or memory consumption, and it follows the same ideology with the time complexity that we have explained in this post.

There is tons of information on the Space Complexity of algorithms online. So do check some out for more information.

But, I hope this explanation on the Big O Notation was clear enough, and in a later post we will discuss how to determine the Big O notation for a piece of algorithm using some examples. 

Prosper, friends

Blog

Blog with us?

Explore