Big-O Notation

First of all, let us understand why the algorithm is needed. What do you think what makes google display the list of thousands of websites when you type in the search box of the search engine? It is an algorithm.

So, algorithms are necessary to solve problems related to computer programming. Nowadays, speed is everything. So, it’s not only the algorithm that you should care about, but it’s also the speed of the algorithm that you should be focusing more.

Time complexity is the amount of time required to execute an algorithm. It is generally expressed using Big-O notation.

Big-O is an asymptotic shorthand mathematical notation that defines the upper bound of an algorithm. It accurately describes the worst-case scenario.

Runtime is not the actual time required to execute code. If it is measured directly, we could express the speed in seconds.

Since we are measuring how quickly the runtime grows, we represent it regarding something else known as Big-O notation where the input size in ‘n’.

For any algorithm having a function g(n), where n is the time to execute the algorithm, we can say the algorithm is O(g(n)).

The algorithms are classified from best-to-worst performance as follows -

  • Logarithmic algorithm – O(logn)
  • Linear algorithm – O(n)
  • Superlinear algorithm – O(nlogn)
  • Polynomial algorithm – O(nc)
  • Exponential algorithm – O(cn)
  • Factorial algorithm – O(n!)
The fastest possible runtime time to execute an algorithm is O(1), commonly known as Constant Running Time.
big-o-comparision-graph

From the graph, you can see that O(n!), O(cn), and O(nc) give us the worst performance in executing the algorithm.

  • Linear algorithm – O(n)
  • :

    O(1) represents an algorithm that always takes the same time regardless of the size of the input.

    Let us look at the following example:

    
    int n = 5;
    System.out.println("Your input is: " + n);
    

    The output of the code is Your input is: 5 which will be printed only once on the screen. So the time complexity is O(1). That means every time constant amount of time is required to execute the code irrespective of what system configuration you are having.

    Polynomial algorithm – O(nc) :

    O(n2) represents an algorithm whose complexity is directly proportional to the square of the input size.

    For example, imagine there are 50 students in a classroom, and one of them has your book with him. You want to find it out. You go and ask the first student in the class if he has it.

    You also ask him about the rest 49 students if they have the book. In that way, you find out who has your book. This is known as O(n2).

    Let’s have a look at this example:

    
     for (int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            System.out.println("Your output is " + i + " and " + j);
        }
    }
    

    If n is 5, then the algorithm will run 52 = 25 times. Now, if we nest another for loop, this would become a cubic algorithm(O(n3)).

    Superlinear algorithm – O(nlogn) :

    O(logn) describes an algorithm whose complexity increases logarithmically as the input size increases. The curve peaks at the beginning and slowly becomes flat as the size of the data increases.

    Consider the same example, now you divide the class into two groups and then ask if the book is on the left side or the right side. Then you one group and again subdivide it into two and ask again, and you keep on repeating that until you find that one student who has your book. This is what you mean by O(logn).

    Let’s have a look at this example:

    
     for (int i = 1; i < n; i = i * 2){
        System.out.println("Your output is " + i);
    }
    

    If n is 8, the output will be :

    
    Your output is 2
    Your output is 4 
    Your output is 8
    

    So, the algorithm ran log(8) = 3 times.

    Linear algorithm – O(n) :

    O(n) is directly proportional to the number of inputs and grows linearly. If you go on asking each student individually till you find out who has your book, this is what we call it as O(n).

    Let us have a look at the following example:

    
    for (int i = 0; i < n; i++) {
        System.out.println("Your output is " + i);
    }
    

    This loop runs for n times.

    Exponential algorithm – O(cn) :

    O(2n) represents an algorithm which doubles with every additional input. Let us have a look at this example:

    
    for (int i = 1; i <= Math.pow(2, n); i++){
        System.out.println("Your output is " + i);
    }
    

    If n is 5, this algorithm will run 25 = 32 times.

    Factorial algorithm – O(n!) :

    O(n!) represents an algorithm whose runtime is proportional to the factorial of the input size.

    Let us have a look at this simple example:

    
    for (int i = 1; i <= factorial(n); i++){
        System.out.println("Your output is " + i);
    }
    
    

    If n is 5, this algorithm will run 5! = 120 times.

    Comparison table of time complexities: big-o-comparision

    Examples of Big-O notations:

    • O(1):- Determining if a number is even or odd.
    • O(logn):- Find an item in a sorted array with a binary search.
    • O(n):- Find an item in an unsorted list.
    • O(nlogn):- Merge sort, quick sort, and heap sort.
    • O(n2):- Traversing a simple 2D array.

    Conclusion

    Big-O notation is very much required to judge the speed of an algorithm with O(n) and O(logn) giving us the best performance in executing an algorithm.

    O(logn) has the same functionality as O(n), but the implementation is completely different and provides us with a better performance with larger inputs.

    About Author

    Myself KarthiQ, I am the author of this blog, I know ways to write a good article but some how I donot have the skills to make it to reach people, would you like help me to reach more people By sharing this Article in the social media.

    Share this Article Facebook
    Comment / Suggestion Section
    Point our Mistakes and Post Your Suggestions

    Copyright © CherCher Tech