What is Big O ?
By definition, big O is the language and metric we use to describe the efficiency of algorithms. Without understanding big O notation it’s not possible to develop efficient algorithms. If you don’t know when your algorithms get faster or slower, you will struggle to judge your program performance. Basically, it gives you the one way of describing half the time that takes to run your application grows as the size of the input grows.
So let’s look at the real life example.
Imagine a scenario where you have a file on your hard drive and you need to send it to your friend and we need to send this file as fast as possible.
How should you send it?
The first thing that comes to our mind is to send it by mail, FTP or some other source of electronic transfer.
This is the correct answer.
If the file size is small, it is faster than to take it to your friend physically. But what if the file is really, really large? Is it possible that it is faster to physically deliver it via a plane? Yes, actually it is.
One terabyte file could take more than one day to transfer it electronically. It would be much faster to just fly it across the country. If it is urgent, you might just want to do it. As you can see, the delivery method is changed based on the file size. This means in the first method, the time that is needed for transfer of a file increases as the size of the file increases.
On the other hand, in the second method where we are taking the file physically, the time that is needed to transfer a file does not depend on the size of the file. It does not matter if you carry one terabyte file or one GB file. The time that is needed for a flight is constant. So in computer science, this is called time complexity.
It’s a way of showing how the runtime of the function increases as the size of the input increases. So if you come back to our example of transferring file to a friend, we can easily see that in terms of time complexity electronic transfer increases linearly with the size of the file.So if the size is increasing and the time that is needed to transfer file is going to be increased. But in case of physical delivery, if the file size is increasing, the time that is needed for delivery is constant. So the time is not changing. Now it’s essential that you understand big O when you go to the technical interview. Because this will absolutely come up.
Now let’s look at them in terms of coding.
So let’s say we have two sets of code, we have code 1 and we have code 2.
So how can we identify which one is better?
Now both of these code are going to accomplish the same thing, but they are written differently. So how do we know that if the code 1 is better than code 2 or if the code 2 is better than code 1? There might be various reasons for this.
The first reason might be that the first code is easier to read or the second code is easier to read. Now if you look at them in terms of big O, the big O is a way of mathematically figuring out which of these code is better, which runs more efficiently.
So obviously we cannot measure these codes over here with the scale.
So I’m going to bring the stopwatch over here to make the point. So let’s say when we are running the first code, we are just starting the stopwatch.
So in this case, the code 1 is running in 30 seconds and the code 2 runs 60 seconds. As you can see, code 1 is performing much more faster than the code 2. Obviously, we want our code to run as quickly as possible. So that’s going to be the efficient code. So by this measure, the code 1 is better than code 2. This is called time complexity. But when we look at the time complexity, we don’t measure the time that. In time complex day, we measure the number of the operations and the reason why we do this is that if you took the same code and run it in the faster computer, it’s obvious that it’s going to take less time. So here, instead of taking the time, we need to look at the number of the operations. So if we run our code in the faster computer or in the slower computer, the number of operations will be the same.
So with big O, we are measuring the number of operations and there is another term which is called space complexity and with big O, we measure the space complexity as well. Now, space complexity is the amount of the memory that some code used. So in terms of time complexity, we said that code 1 is performing in 30 seconds and code 2 is performing in 60 seconds.
But when we are performing the code 1 , it is possible that we are using more memory and when we are executing the code 2, it takes the less memory. So if we look at the in terms of space complexity, we will see that in this case code 2 is better than code 1. Because it is using less memory.
There are various types of runtime complexity such as O(N), O(logN) and so on. So we are going to look them separately. But if we look at the time complexity, for example, painting this wall where the weight is w and the height is h , so the time complexity can be expressed like this : O( wh). So it’s very crucial that our programs run fast , because they’re not executed in supercomputers.
For example, if you look at the mobile app users that face the slow performance from the app, they tend to quit and delete the app.
We need to have a proper algorithm to choose for our development to make faster applications.
We will go in detailed on Big O and others in upcoming articles