Big-Oh or Big O notation with Java examples

Big-Oh notation is an asymptotic notation that allows us to characterize the performance of an algorithm. In simple terms, it is calculated based on the count of the operations performed when the input grows. For example, if the number of operations remain constant irrespective of the value of the input then the function has a time complexity of an Order of 1 or O(1).

Below are some of the commonly used Big-Oh notations in the order of high to low performance.

O(1)constant time
O(log2 n)logarithmic
O(n)linear
O(n2)quadratic
O(cn)exponential
O(n!)factorial
O(1) – Constant time complexity

Consider the below java code. It prints whether the input value is an even or odd number. The number of operations are same for n = 1 or n = 100000. So this functions has O(1) Constant time complexity. 

public void evenOrOdd(int n){
    if(n%2==0){
        System.out.println("Even number");
    }else{
        System.out.println("Odd number");
    }
}
O(log2 n) – Logarithmic

Consider the below java code. The function is doubling the number and printing. If n = 4 then it prints 2 times, if n = 8 it prints 3 times, if n=16 it prints 4 times and so on. For n = 4, the number of operations 2 = log2 4 and in the same way for n = 8, the number of operations 3 is log2 8 and hence the complexity of this function can be best denoted as O(log2 n) or O(log n).

public void doubleTheNumbers(int n){
    for(int i = 1 ; i < n ; i = i * 2){
        System.out.println(i);
    }
}
O(n) – Linear time complexity

Consider the below java code. It is trying to find out the max number in an unsorted array. If the array size is 1 then the if logic will be executed only once. If the array size is 10 then if logic will be executed 10 times. So the time complexity of this function is O(n) which can be said as Order of n.

public void arrayMax(int[] array){
    int maxValue=0;
    for(int i = 0; i < array.length ; i++){
        if(i==0 || maxValue < array[i]){
            maxValue = array[i];
        }
    }
    System.out.println("maxValue" + maxValue);
}

Consider below java code. There are 2 for loops. First one prints 10 times and second one prints n number of times. So the time complexity can be denoted as O(n + 10). But for Big O notation we should consider worst case scenario like n = 1 million. In that case 10 is ignorable. So the Big O notation for this function would be denoted as O(n) and not as O(n + 10).

public void twoForLoops(int n){
    for(int i = 0; i < 10 ; i ++){
        System.out.println(i);
    }
    for(int i = 0 ; i < n ; i++){
       System.out.println(i);
    }
}
O(n + m) – Linear additive.

Consider the below java code. If n = 2 and m = 3 then it prints 2 + 3 = 5 times. Hence the time complexity can be denoted as O(n+m).

public void twoForLoops(int n, int m){
    for(int i = 0 ; i < n ; i++){
      System.out.println(n);
    }
    for(int i = 0 ; i < m ; i++){
        System.out.println(m);
    }
}
O(n*m)

Consider the below java code. If n =2 and m = 3 it prints 2 * 3 = 6 times. Hence the time complexity of this function can be denoted as O(n*m).

public void nestedForLoops(int n, int m){
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            System.out.println("i " + i + " j" + j);
        }
    }
}
O(n2) – Quadratic

Consider the below java code. It is a simple nested for loop. If n = 2, it prints 4 times, if n = 4 it prints 16 times and so on. Hence the time complexity of the function is O(n2).

  public void nestedForLoop(int n){
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                System.out.println("i " + i + " j " + j);
            }
        }
    }

For a graphical view of Big O refer this web page

%d bloggers like this: