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(N2) = 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(N2)

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.

Advertisements

14 thoughts on “An Intro to Big Oh Notation with Java

  1. Pingback: Big O notation - Java Forums
  2. its looks like magic,what are the costs and the n time each java statement makes.thank you for your anticipated reply/answer.

  3. hey!I observed the previous post(your inspiration)..but that was also written in Java.It had bool return type and String as a data type.
    But i think your post was as good as your inspiration..The graphs did help me a lot.:-)

  4. Hey, I came here also from the aforementioned inspiration link, but i gotta say, that graph was really what I needed to tie it all together. Thanks for the effort!

    (Also I don’t speak Java very fluently and your examples were perfectly clear to me, so good work there as well)

  5. Just one minor correction: Your entry for “O(N^2) = growth will double with each additional element in the input” is confusing O(N^2) with O(2^N). The description is correct for the latter. For the former, you would say that time complexity increases proportional to the square of the size of the input set.

  6. Good post. One minor correction

    The value under the cubic column for 1,048,576 should be 10 to the power 18, not 10 to the power 16.

    Exponent 16 should be changed to 18.

  7. Pingback: Algorithm basics – avoid nested loops and divide and conquer often | Apprenticecoder's Blog
  8. Thanks you for this post !
    Just a detail but you should use “equals” when compare 2 strings.
    For example: if (args[i] == value) should be if( args[i].equals(value))

  9. The topic has been explained in a very lucid manner. Thank you very much for making me understand the concept. It would be of great help to me as I am having my examination tomorrow.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s