Why is using sorting (O(n log n) complexity) to find the majority element faster than using a HashMap (O(n) complexity)?

Question

Majority element question:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

// Solution1 - Sorting ----------------------------------------------------------------
    class Solution {
        public int majorityElement(int[] nums) {
            Arrays.sort(nums);
            return nums[nums.length/2];
        }
    }

// Solution2 - HashMap ---------------------------------------------------------------
class Solution {
    public int majorityElement(int[] nums) {
        // int[] arr1 = new int[nums.length];
        HashMap<Integer, Integer> map = new HashMap<>(100);  
        Integer k = new Integer(-1);
        try{
            for(int i : nums){
                if(map.containsKey(i)){
                    map.put(i, map.get(i)+1);
                }
                else{
                    map.put(i, 1);
                }
            }
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                if(entry.getValue()>(nums.length/2)){
                    k = entry.getKey();
                    break;
                }
            }
        }catch(Exception e){
            throw new IllegalArgumentException("Error");
        }
        return k;    
    }
}

The Arrays.sort() function is implemented in Java using QuickSort and has O(n log n) time complexity.

On the other hand, using HashMap to find the majority element has only O(n) time complexity.

Hence, solution 1 (sorting) should take longer than solution 2 (HashMap), but when I was doing the question on LeetCode, the average time taken by solution 2 is much more (almost 8 times more) than solution 1.

Why is that the case? I'm really confused.....

Is the size of the test case the reason? Will solution 2 become more efficient when the number of elements in the test case increases dramatically?

Answer 1

Big O isn't a measure of actual performance. It's only going to give you an idea of how your performance will evolve in comparison to n.

Practically, an algorithms in O(n.logn) will eventually be slower than O(n) for some n. But that n might be 1, 10, 10^6 or even 10^600 - at which point it's probably irrelevant because you'll never run into such a data set - or you won't have enough hardware for it.

Software engineers have to consider both actual performance and performance at the practical limit. For example hash map lookup is in theory faster than an unsorted array lookup... but then most arrays are small (10-100 elements) negating any O(n) advantage due the extra code complexity.

You could certainly optimize your code a bit, but in this case you're unlikely to change the outcome for small n unless you introduce another factor (e.g. artificially slow down the time per cycle with a constant).

(I wanted to find a good metaphor to illustrate, but it's harder than expected...)

Answer 2

It depends on the test cases, some test cases will be faster in HashMap while others not.

Why is that? The Solution 1 grantee in worst case O(N log₂ N), but the HashMap O(N . (M + R)) where M is the cost of collisions and R the cost of resizing the array.

HashMap uses an array named table of the nodes internally, and it resizes different times when the input increase or shrink. And you assigned it with an initial capacity of 100.

So let see what happens? Java uses Separate chaining for resolving the collisions and some test cases may have lots of collisions which lead to consuming lots of time when a query or update the hashmap.

Conclusion the implementation of hashmap is affected by two factors: 1. Resize the table array based on the input size 2. How many collision appears in the input