An Intro to Big Oh Notation with Java

Big Oh notation is used in computer science to decribe the complexity of an algorithm in terms of time and space (memory). Big Oh notation describes the worst case scenario of what happens when an algorithm is run with N values and is really only useful when talking about large sets of data.

	constant	logarithmic	linear		quadratic	cubic
n	O(1)	O(log N)	O(N)	O(N log N)	O(N2)	O(N3)
1	1	1	1	1	1	1
2	1	1	2	2	4	8
4	1	2	4	8	16	64
8	1	3	8	24	64	512
16	1	4	16	64	256	4,096
1,024	1	10	1,024	10,240	1,048,576	1,073,741,824
1,048,576	1	20	1,048,576	20,971,520	1012	1016

Big Oh Complexity Over Time

Source: table source here also big thanks to Dean who made the graph for me 🙂

Explanation

O(1) = irrespective of changing the size of the input, time stays the same

O(N) = as you increase the size of input, the time taken to complete operations scales linearly with that size

O(log N) = growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase

O(N²) = growth will double with each additional element in the input

Java Example for O(1):

    public static boolean isArrayOver100(String[] args) {
        if (args.length > 100)
            return true;
        return false;
    }

Java Example for O(N):

    public static boolean contains(String[] args, String value) {
        for (int i = 0; i < args.length; i++) {
            if (args[i] == value)
                return true;
        }
        return false;
    }

Java Example for O(log N):

public static int binarySearch(int[] toSearch, int key) {
    int fromIndex = 0;
    int toIndex = toSearch.length - 1;

    while (fromIndex < toIndex) {
        int midIndex = (toIndex - fromIndex / 2) + fromIndex;
        int midValue = toSearch[midIndex];

        if (key > midValue) {
            fromIndex = midIndex++;
        } else if (key < midValue) {
            toIndex = midIndex - 1;
        } else {
            return midIndex;
        }
    }
    return -1;
}

See my other post on binary search here.

Java Exmaple O(N²)

public static boolean containsDuplicates(String[] args) {
        for (int i = 0; i < args.length; i++) {
            for (int j = 0; j < args.length; j++) {
                if (i == j)
                    break;
                if (args[i] == args[j])
                    return true;
            }
        }
        return false;
    }

I took this post as my inspiration as I found it to be a great introduction but have instead used java for the code examples.

• algorithms
• code
• J2EE