2

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?

JohnWinter
  • 1,003
  • 5
  • 12
  • 25
  • look at the source, if you cannot then feed huge lists and measure times (for time complexity at least).Tthere are tools that monitor heap/stack usage, one of the simplest is build in jdk "jconsole" located in the bin directory – Palcente Jun 20 '15 at 18:23
  • Do you know how to calculate the O complexity of each one? If you do, then comparing them should be pretty easy. If you don't, then please edit your question to reflect that, because the wording seems to suggest you do. I'm not sure what the question really is. – yshavit Jun 20 '15 at 18:28
  • @Palcente I always thought that algorithm complexity it is a thing which related to some theory and not to the practice. – JohnWinter Jun 20 '15 at 18:28
  • @yshavit I don't know how to do it. – JohnWinter Jun 20 '15 at 18:29
  • Which one? Both? What resources for calculating big O have you read, and what don't you understand about applying those here? This question is very broad so far, basically "how do I calculate big O" -- too broad for SO's format. – yshavit Jun 20 '15 at 18:32
  • @yshavit https://en.wikipedia.org/wiki/Big_O_notation – JohnWinter Jun 20 '15 at 18:32
  • Btw, you should be aware that the two methods don't behave the same. The first Kris the order of the list, while the second returns a list in essentially random order because HasSet doesn't have a defined order of iteration. – yshavit Jun 20 '15 at 19:03
  • @yshavit If I'll change `HashSet` to `LinkedHashSet` will that fix the problem? – JohnWinter Jun 20 '15 at 19:08
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/81090/discussion-between-johnwinter-and-yshavit). – JohnWinter Jun 20 '15 at 20:35

3 Answers3

2

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.

StanislavL
  • 56,971
  • 9
  • 68
  • 98
  • All of which is learned from looking at the implementation of ArrayList and HashSet (or believing what Javadoc says). It would be possible to add something to ArrayList which would make contains O(1). – laune Jun 20 '15 at 18:49
  • 1
    @laune no. contains() for list checks all elements. In fact iterates through the list. Of course it's possible to add something ... but that would not be ArrayList – StanislavL Jun 20 '15 at 18:53
  • Of course I know what java.util.ArrayList.contains does. Please read what I wrote: I said **it would be possible** and that you need to be **looking at the implementation** to be sure. OP seemed to doubt the necessity of looking at the implementation. Adding something to ArrayList wouldn't make it lose its contract, i.e. its implementated interfaces. – laune Jun 20 '15 at 18:56
  • @laune See for example http://stackoverflow.com/questions/5771740/time-complexity-of-containsobject-o-in-an-arraylist-of-objects if you modify list to have constant time contains() it wuld mean you somehow should merge list and set whch in turn leads us to the approach 2. – StanislavL Jun 20 '15 at 19:02
  • Hey, that's what I was trying to say :-) You need to look at the actual implementation. I think that was Palcente's advice. – laune Jun 20 '15 at 19:12
  • @laune You don't have to look at the implementation -- the javadocs say that all operations other than add, size, isEmpty, get, set, iterator, and listIterator "run in linear time (roughly speaking)." – yshavit Jun 20 '15 at 21:16
  • @yshavit ...which is what I wrote in my first comment. – laune Jun 21 '15 at 05:09
0

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).

Abhijeet Dhumal
  • 1,799
  • 13
  • 24
0

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.

Dean J
  • 39,360
  • 16
  • 67
  • 93