LinkedHashMap complexity

Question

i have simple problem to find the first unique element in array A. But, what bothers me is the time complexity using different methods. I've tried this two methods so far.

First Method:

LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();
return -1;

Second Method:

    for(int i=0; i< A.length; i++){
        boolean unique = true;
        nestedFor:for(int j=0; j< A.length; j++){
            if(i != j && A[i] == A[j]){
                unique = false;
                break nestedFor;
            }
        }
        if(unique)
            return A[i];
    }
    return -1;

Testing with array of 1000000 elements, the first method executes at ~2000ms, while the second at ~10ms. My question is: shouldn't the first method executes faster since its complexity is O(nLogn) compared to second method which complexity is O(n^2)? What am i missing here ? Below the test code:

    int[] n = new int[1000000];
    for (int i = 0; i < n.length; i++)
        n[i] = new Random().nextInt(2000000);

    long start = System.currentTimeMillis();
    firstUnique(n);
    System.err.println("Finished at: " + (System.currentTimeMillis() - start ) + "ms");

EDIT:

for (int i = 0; i < A.length; i++)
{
    if (!map.containsKey(A[i]))
        map.put(A[i], new ArrayList<>());
    map.get(A[i]).add(i);
}

Consumes 99% of execution time, while

for (Map.Entry<Integer, List<Integer>> m : map.entrySet())
    if (m.getValue().size() == 1)
        return m.getKey();

is always 1-3ms. So, yes filling the map is the most expensive operation.

What would you suggest as most efficient method for this kind of problem?

Answer 1

I suspect that you are not picking inputs which create "worst case" conditions for the second case.

For instance, if you construct the array such that all of the million elements have a duplicate (e.g. A[i] = 2 * i / A.length), then the second method is way, way slower than the first, since it has to check 10^12 combinations of elements.

You can make it a bit faster (roughly twice as fast) by changing the condition on the inner for loop to only check from j = i + 1, but 10^12 / 2 is still a pretty big number.

If you are simply picking random numbers to populate the array, there is a reasonable chance that the first element is unique, and a greater chance that one of the first and second elements is unique, etc. After a few elements, you'll reach near-certainty that the element is unique, so it will stop after a few iterations.

---

The 2 seconds taken for the first method is way too long. I can only think that you're not warming up your JIT correctly before the benchmark. But even without trying to do that, your first method only takes 40-50ms for me (dropping to 10-15ms after a few iterations).

Most of this time will be due to object creation - both in the autoboxing of the keys and values, and in the creation of the ArrayList instances.

Answer 2

Time complexity ignores coeffecients because often it is more useful to know how a function grows with increasing input sizes. Although your first function has a lower time complexity, at small input sizes, it will run much slower because you are making many ArrayList objects which is computationally expensive. Your second method however only uses array accesses which is much less expensive than instantiating an object.

Answer 3

Time complexity is meant to be understood in its asymptotic sense (i.e. as input sizes grow to googolplex), and nothing else. If an algorithm has linear time complexity, that only means that there is some a,b such that executiontime (roughly !!!) = a * inputsize + b. It says nothing about the actual magnitude of a and b, and two linear algorithms can still have massive performance differences because the magnitudes of their a/b differ vastly.

(Also, your example is a poor one because time complexity of an algorithm should take into account the complexity of all the underlying operations such as object creation and the like. Others have hinted at that in their answers too.)

Answer 4

Consider using 2 sets instead:

public int returnFirstUnqiue(int[] a)
{
  final LinkedHashSet<Integer> uniqueValues = new LinkedHashSet<Integer>(a.length);
  final HashSet<Integer> dupValues = new HashSet<Integer>(a.length);

  for (int i : a)
  {
    final Integer obj = i;
    if (!dupValues.contains(obj))
    {
      if (!uniqueValues.add(obj))
      {
        uniqueValues.remove(obj);
        dupValues.add(obj);
      }
    }
  }

  if (!uniqueValues.isEmpty())
  {
    return uniqueValues.iterator().next();
  }
  return -1;
}

Answer 5

First as to why the benchmark isn't relevant:

• Even if we ignore inaccuracies caused by used method, GC etc., finding out that method 2 is faster on a million entries won't tell you anything about how it will perform on a billion of entries
  • Big-O is a theoretical concept and has to be proved theoretically. Most a benchmark can do for you here is let you estimate the complexity, and that would be done not by comparing two methods on one input, but by comparing one method on multiple inputs, each an order of magnitude larger than the previous (and even then it's near impossible to draw any useful conclusions)
• Big-O is a worst-case complexity, but your random input is likely to be somewhere "in the middle" for the first method (map), while it will be far from worst case for the array - actually it has 50% chance of succeeding on first iteration, while the map has to be fully processed and will in average have about half a million entries
  • the worst case for the "map" method would probably be all elements different but with equal hashcode (so you would need to read the whole list of added elements in each of the n iterations)
  • the worst case for the "array" method is all elements being equal (need complete the whole nested iteration)

---

As to finding a good algorithm - you could use a Map<Integer, Boolean> instead of Map<Integer, List<Integer> since you only need to store the unique flag and not a list of values - add with True when you see the element first time, switch to False when you encounter a duplicity

• LinkedHashMap operations put, containsKey/get have big-O complexity O(n) (worst-case) making the whole algorithm O(n^2)
• However, the amortized complexity of put is O(1) (making amortized complexity of all insertions O(n)) and average complexity of get is constant (this depends on how well the hash function used works for the inputs given); unique value lookup is then O(n)

Answer 6

My observations: Second method is much quicker because it is using Array with declared width. In First example there are changes of the size happenings.

Please try to define more accurate size of LinkedHashMap to set initial capacity equal to 1000000.

Next thing here is that Array is much simpler structure where GC is not trying to do anything. But when it comes to LinkedHashMap its more complex and cost of creating it and manipulating is far much complex in some cases than simple getting element at particular index from Array.