ChatGPT, é você?
Embora boa parte do que está escrito aí esteja correto, acaba tendo pouca utilidade prática. E não tem benchmark algum aí, a não ser o nome do namespace.
Se testar exatamente estes códigos, como parece que fez, testará várias coisas que não são o uso das estruturas de dados citadas, por exemplo o custo altíssimo de fazer IO no console. Outros fatores podem afetar o teste se não entender bem como a implementação é feita e evitar certas armadilhas, por exemplo o que acontece qiando estoura a capacidade atual reservada,m quando algo é feito em certa ordeme ou outra.
Além disso, usa estruturas muito pequenas onde não faz diferença alguma, o custo geral é muito maior do que as operações individuais, que é o que fará sua aplicação ser mais eficiente ou menos em cada caso. Para um n muito baixo, como 3, o Big O é irrelevante.
Se for medir a performance de forma adequada precisa de uma ferramenta mai sofisticada, além de produzir códigos que possam medir só oque interessa. O Benchmark dotNET é a mais indicada.
Enfim, e parafraseando meu amigo ChatGPT, em resumo, benchmarks são muito mais complexos que isso, e feitos de forma errada dá informação pior que nenhuma informação. Obrigado pela tentativa do autor, e oportunidade de colocar essa ressalva importante.
Referência que ajuda entender as complexidades de cada estrutura.
Farei algo que muitos pedem para aprender a programar corretamente, gratuitamente. Para saber quando, me segue nas suas plataformas preferidas. Quase não as uso, não terá infindas notificações (links aqui).