Understanding the Problem: The O(M*N) Nested Search Bottleneck

When matching data between two lists in C#, a common beginner mistake is using LINQ methods like .First(), .FirstOrDefault(), or .Where() inside a foreach loop. Consider this scenario where you have a large list List1 containing $N$ records that need an Id populated from a reference list List2 containing $M$ records:

foreach (var item in List1)
{
    var found = List2.First(y => y.EnglishName == item.EnglishName);
    item.Id = found.Id;
}

Because List2.First(...) performs a linear scan across List2 for every single element in List1, the total time complexity scales to O(N × M). If List1 has 100,000 items and List2 has 10,000 items, your application performs up to 1,000,000,000 comparisons. This causes significant performance bottlenecks and high CPU utilization.

The Solution: Achieving the O(N + M) Lower Bound with a Dictionary

The true lower bound for this problem is O(N + M) time complexity. To match every item in List1, you must inspect all $N$ items at least once. Similarly, to access reference data from List2, you need to read its $M$ items at least once.

You can achieve this optimal lower bound by converting the reference list (List2) into a hash-based lookup structure, such as a Dictionary<TKey, TValue>, before iterating over List1.

Refactored Code Using a Dictionary

// Step 1: Pre-index List2 into a Dictionary (O(M) time and O(M) space)
var lookup = List2.ToDictionary(x => x.EnglishName, x => x.Id);

// Step 2: Update List1 with O(1) average lookup time per item (O(N) time)
foreach (var item in List1)
{
    if (lookup.TryGetValue(item.EnglishName, out var id))
    {
        item.Id = id;
    }
}

Why This Approach is Significantly Faster

  • O(M) Setup Time: Converting List2 into a Dictionary<string, int> processes the $M$ elements once and inserts them into a hash table.
  • O(1) Lookup Time: Accessing a value by key using TryGetValue or indexers operates in average O(1) constant time.
  • O(N) Processing Time: Iterating through List1 takes $N$ operations, with each step costing O(1).
  • Total Time Complexity: O(N + M), reducing execution time from minutes or seconds down to milliseconds.
  • Space Complexity: O(M) auxiliary memory, which is a worthwhile trade-off for massive performance gains.

Alternative Approaches

1. String Comparison Considerations

By default, string hashing and comparison in .NET are culture-sensitive. If your English names should match regardless of casing, pass an IEqualityComparer to your dictionary:

var lookup = List2.ToDictionary(
    x => x.EnglishName, 
    x => x.Id, 
    StringComparer.OrdinalIgnoreCase
);

2. Handling Non-Unique Keys with Lookup

If List2 is not guaranteed to contain unique keys in the future, ToDictionary() will throw an ArgumentException. In that case, you can use ToLookup():

var lookup = List2.ToLookup(x => x.EnglishName, x => x.Id);

foreach (var item in List1)
{
    item.Id = lookup[item.EnglishName].FirstOrDefault();
}

Summary

Whenever you need to correlate two collections in memory, avoid nested linear searches like List.First() or nested foreach loops. Index the lookup source into a Dictionary<TKey, TValue> to reduce the algorithmic complexity from O(N × M) to O(N + M).