Firstly, before talking about Big O Notation we should try to answer the following question,
“How do we compare different algorithm implementations in order to choose the best solution for our application?”
It’s simply by Run-time. We need to find algorithm which takes the minimum amount of run-time to solve that particular problem.We can measure run-time by using a stop watch. But it’s not practical enough. Because we have to run the code all the time to measure the run-time.So the best solution is code analysis. We can measure the run-time just by looking at the code.
But the next question we come across would be,
“How to do code analyzing to check run-time?”
For that we use big O notation. Which is explained in the example below.
Example 01 :
If there is an algorithm like below.
We put values to each statement like below.
So the total run-time value is the sum of all the above values.
So in here ct1 and ct2 are numeric values.
The complexity of the above algorithm is O(n).
There are so many types of big O notations. N, n2, n3 are the most common types.
Below explains how we decide the complexity according to the big O notation
When considering big o notation time changes according to the data input as the below diagram.
As the n increases the time is also increasing gradually according to that. The following table explains the big o notations summary.
written by Binu Senevirathne