Is my Java solution O(n) or am I missing something?

My solution for a certain problem is apparently slower than 95% of solutions and I wanted to make sure that I was correct on the time complexity.

It looks to me like this code is O(n). I use a couple of loops that are at most O(n) and they aren’t nested so I don’t believe the solution is n^2.

I use a HashMap as storage and use HashMap methods which are O(1) inside my while and for-loop for insertion and look ups respectively.

Am I correct in that this solution is O(n) or am I missing something?

 public int pairSum(ListNode head) {
    
    HashMap<Integer, Integer> nodeVals = new HashMap<Integer, Integer>();
    
    int count = 0;
    
    ListNode current = head;
    nodeVals.put(count, current.val);
    count++; 
    
    while (current.next != null) {
        current = current.next;
        nodeVals.put(count, current.val);
        count++;
    }
    
    int maxTwinSum = 0;
    for (int i = 0; i < nodeVals.size() / 2; i++) {
        int currTwinSum;
        currTwinSum = nodeVals.get(i) + nodeVals.get(nodeVals.size() - 1 - i);
        if (currTwinSum > maxTwinSum) maxTwinSum = currTwinSum;
    }
    
    return maxTwinSum;
}

Answer

Is my Java solution O(N) or am I missing something?

Yes to both!

Your solution is O(N), AND you are missing something.

The something that you are missing is that complexity and performance are NOT the same thing. Complexity is about how some measure (e.g. time taken, space used, etc) changes depending on certain problem size variables; e.g. the size of the list N.

Put it another way … not all O(N) solutions to a problem will have the same performance. Some are faster, some are slower.

In your case, HashMap is a relatively expensive data structure. While it it (amortized) O(1) for operations like get and put, the constants of proportionality are large compared with (say) using an ArrayList or an array to hold the same information.

So … I expect that the solutions that are faster than yours won’t be using HashMap.

---

The flipside is that an O(N^2) solution can be faster than an O(N) solution if you only consider values of N less than some threshold. This follows from the mathematical definition of Big O.

For instance, if you are sorting arrays of integers and the array size is small enough, a naive bubblesort will be faster than quicksort.

---

In short: complexity is not performance.