How to compare the complexity of two methods in Java?

Question

How can I compare the O complexity of these two methods?

Here is the first method:

protected static List<Integer> removeDuplicates1(List<Integer> source) {
    List<Integer> tmp = new ArrayList<Integer>();
    for (Integer element : source) {
        if (!tmp.contains(element)) {
            tmp.add(element);
        }
    }

    //Collections.sort(tmp);
    return tmp;
}

And the second one:

protected static List<Integer> removeDuplicates2(List<Integer> source)  {
    return new ArrayList<Integer>(new HashSet<Integer>(source));
}

UPD

I don't know how to calculate the O complexity of both methods.

UPD2

Ok, the time complexity of the first method is O(n^2), the second is O(n). And what about memory usage? Who is more greedy and why?

Answer 1

The second is better O(n) complexity (O(n^2) for the first).

For the first you go through the list in the loop (n) and for each operation run contains() which in turn goes through the tmp list to find whether the element is there (one more n).

For the second method operations of adding in the Set is constant so in fact just one n.

Answer 2

Second method works better as its complexity is O(n) as against of first where it runs in O(n^2).

The complexity of the second solution in case of Big O notation is O(n) as it loops through the List only once. While in the first case it first for loop runs once but internal contains mehtod again runs on a temporary list. So the complexity in this case is O(n^2).

Answer 3

Don't try to do this in Java, just try to do it in pseudocode.

In the first question, you have two Lists of Integers; two lists of numbers. If there aren't any other rules given, we can assume that both lists are about n items long.

You're walking all the way through one of the lists, and doing something for each number in it. If there are n numbers, that's n steps. For each of those n steps, you're saying "does the other list have this number?"

To check and see if a list has a number in it, the worst case is that it doesn't, which means you have to check each item in the list to find out. That's also n steps, if the second list can be about as big as the first.

Putting those together: Walking through a list of n items, and doing n things on each item.

Let me know what you think that comes up to, and I'll edit this answer after that.

For your second code snippet, split it up.

The first thing to happen is that you create a HashSet using all the items in the input. How long does it take to insert one item to a HashSet? If you insert n items, multiply the time for a single insert by n.

The second thing that happens is the new ArrayList is called. Checking the API to be sure of what it's doing: http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#ArrayList(java.util.Collection)

It's creating an ArrayList using all of the items in the HashSet Collection. How long does it take to insert to an array list? Multiply that by the number of items (n) to get the answer.

Since these happen as separate steps, they're separate things. Whichever has a higher big-O complexity is the dominant one, and you can ignore the other. If they both have the same big-O complexity, that's the answer; you can ignore one, as O(2n) is the same complexity as O(n); constants (like 2x) get dropped.