On my path learning data structure, I thought It’d be nice to make a post with a quick explanation about Big O notation with Java examples.

Light

What is Big O?

Big O is used for measure the time complexity of an algorithm. It helps to understand how efficient is the code, dealing with the worst scenario, as the good scenario does not tell us much.

O(n)

public static void printItems(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(i);
    }
}

Drop Constants

public static void printItems(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println(i);
    }

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

O(n^2)

public static void printItems(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                System.out.println(String.format("%s, %s, %s",i,j,k));
            }
        }
    }
}

O(1)

public static int printItems(int n) {
    return n + n + n;
}

(log n)

public static void printItems(int n) {
    for (int i = 1; i < n; i = i * 2){
        System.out.println(i);
    }
}

References:

  • https://www.baeldung.com/java-algorithm-complexity
  • https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/