Table of content

Big-O Notation in Java

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 on more. Understanding the complexity of an algorithm can affect the running time of your code.

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.

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

The output 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 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) :

Exponential Time complexity denotes an algorithm whose growth doubles with each addition to the input data set.

An example of O(2n) time algorithm:

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

If n=8, this algorithm will run 28 = 256 times.

Factorial Algorithm - O(n!) :

The factorial algorithm has a run time proportional to the factorial of the input size.

A common example of this algorithm is TSP(Travelling Salesman Problem).

A simple example of the factorial algorithm is-

// factorial(n) simply calculates n!
for (int i = 1; i <= factorial(n); i++){                                
    System.out.println(i);
}

If n is 8, this algorithm will run 8! times.

0 results
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions