Remove duplicated in array with best performance I am trying to remove duplicates from an array using the following two algorithms

   void PrintDuplicates(int[] arr)
   {
       if (arr == null)
           throw new ArgumentException("arr can't be null.");

       Hashtable table = new Hashtable();

       for (int i = 0; i &lt; arr.Length; i++)
       {
           if (table.ContainsKey(arr[i]) == true)
           {
               // Console.WriteLine(i);
           }
           else
           {
               table.Add(arr[i], "");
           }
        }
    }

    void PrintDuplicatesWithSort(int[] arr)
    {
        if (arr == null)
            throw new ArgumentException("arr can't be null.");

        arr.ToList().Sort();

        for (int i = 0; i &lt; arr.Length - 1; i++)
        {
            if (arr[i] == arr[i + 1])
            {
                // Console.WriteLine(i);
            }
        }
    }


Time complexity of the first algorithm to my understanding is O(n), while time complexity of the second is O(n) for sorting plus O(n-1) for the loop meaning total of O(2n-1).

However when I benchmark the code on this array int[] arr = { 4, 2, 5, 4, 1 }; the one with the higher complexity performs two times better. This implementation is using .net which uses insertion sort and implementation of hashtable that searches in O(1) according to their documentation. What am I missing here?
Sorting is $O(n\log n)$, not $O(n)$.

Also these are asymptotic bounds. Even if one algorithm is $O(n)$ and another is $O(n^2)$, it is possible that, for small-ish values of $n$ the second algorithm is faster.

More concretely, $f(n) = 1000 n$ is $O(n)$ and $g(n)=n^2/1000$ is $O(n^2)$, and both bounds are tight. Still, it will take a while for the first function to become smaller than the second one: for $n&lt;1000000$ the second one is smaller.