O que é mais rápido e devo sacrificar o padrão Linq para obter velocidade (assumindo que a pesquisa no Dicionário seja realmente mais rápida)? Então deixe-me elaborar:

Eu tenho o seguinte:

List<Product> products = GetProductList();

Preciso procurar um produto com base em algum atributo, por exemplo, o número de série. Eu poderia primeiro criar um dicionário e preenchê-lo da seguinte maneira:

Dictionary<string, Product> dict = new Dictionary<string, Product>();
foreach(Product p in products)
{
    dict.Add(p.serial, p);
}

Quando chegar a hora de encontrar um produto, aproveite o O (1) oferecido pela pesquisa no Dicionário:

string some_serial = ...;
try { Product p = dict[some_serial]; } catch(KeyNotFoundException) { }

Como alternativa, usando o Linq:

Product p = products.Where(p => p.serial.Equals(some_serial)).FirstOrDefault();

A desvantagem da abordagem Dict é, obviamente, que isso requer mais espaço na memória, mais código para escrever, menos elegante etc. (embora a maior parte disso seja discutível). Suponha que isso não seja fator. Devo adotar a primeira abordagem?

Para concluir, gostaria de confirmar se a complexidade da abordagem Linq acima é realmente O (n) e não vejo como ela pode ser melhor que isso.