Optimize Code to O(n)

At Bentley Systems, the IFC model-import pipeline scans every newly uploaded building model for duplicate component IDs before it gets merged into the project database. A reused ID across two elements corrupts the clash-detection reports that structural and MEP engineers rely on, so this scan runs on every upload, including models with well over 200,000 elements.

The check below works correctly but takes minutes to run on large models and is timing out the import job. It needs to run in O(n) time on the number of component IDs.

public class DuplicateComponentChecker
{
    public List<string> FindDuplicateComponentIds(List<string> componentIds)
    {
        var duplicates = new List<string>();

        for (int i = 0; i < componentIds.Count; i++)
        {
            for (int j = 0; j < componentIds.Count; j++)
            {
                if (i != j && componentIds[i] == componentIds[j])
                {
                    if (!duplicates.Contains(componentIds[i]))
                    {
                        duplicates.Add(componentIds[i]);
                    }
                }
            }
        }

        return duplicates;
    }
}

Explain in detail why this implementation is so slow, and describe how you would rewrite it to run in O(n) time. You do not need to submit code, just walk through your reasoning and the approach you would take.