Big O equivalence for LINQ select

Question

I'm trying to determine if there is a change in the Big O equivalence of a nested loop when I use a LINQ select instead.

public void myFunc(List<Foo> fooList, List<Bar> barList)
{
    foreach(Foo foo in fooList)
    {
        foreach(Bar bar in barList)
        {
            if(foo.PropA == bar.PropA && bar.PropZ.HasValue)
                foo.PropC = foo.PropB * bar.PropZ;
        }
    }
}

I believe this nested loop example is O(n^2) for complexity.

I replaced the nested loop with a LINQ select like this:

public void myFunc(List<Foo> fooList, List<Bar> barList)
{
    foreach(Foo foo in fooList)
    {
        Bar bar = (from b in barList
                    where foo.PropA == b.PropA
                    select b).FirstOrDefault();

        if(bar.PropZ.HasValue)
            foo.PropC = foo.PropB * bar.PropZ;
    }
}

If nothing else, the code appears to be a little cleaner to read as it explicitly states "we're looking for this particular Bar to work with."

My question is this: Does using the LINQ select reduce the Big O complexity?

Answer 1

Big O is the same, since both codes will (in the worst case) have to perform a comparison for each combination of items from both lists. For example, if there are no matches between the lists, no optimization in the Linq implementation will avoid having to check all items.

But hey, you don't really want to know about big-O, do you? You want to know if the second one is faster. The answer is yes, the linq-based solution is faster (as long a n is big enough) because it only have to perform the check until the first match in the list is found, while the nested-for solution always have to visit all items. The Where method doesn't scan the whole list immediately but rater creates a lazy iterator. The FirstOrDefault method then executes the iterator until the first match is found, which means that in the common case it doesn't have to traverse the whole list. Of course there is some overhead in the Linq solution, so if n is low enough the nested-for loop will be faster.

You can check out the source yourself: https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Enumerable.cs

(But if you added a break in the first sample, the two codes would be semantically equivalent, and the first one would be faster due to less overhead.)

Answer 2

No difference in complexity, both are O(n²) because Linq's Where is O(n).
The use of FirstOrDefault is equivalent to do this :

if(foo.PropA == bar.PropA && bar.PropZ.HasValue) 
{
    foo.PropC = foo.PropB * bar.PropZ;
    break;
}

This is an improvement on the calculation time, but not on the complexity.

You can do better by using an Hashmap for one of the two list's.
The Linq's Join operator will create a Hashmap for one of the 2 lists, so you will gain on performance when searching two matching element :

    public void myFunc(List<Foo> fooList, List<Bar> barList)
    {
        var rows = fooList.Join(
                        barList, 
                        f => f.PropA, 
                        b => b.PropA, 
                        (f, b) => new { Foo = f, Bar = b }
                   );

        foreach (var row in rows)
        {
            if (row.Bar.PropZ.HasValue)
                row.Foo.PropC = row.Foo.PropB * row.Bar.PropZ.Value;
        }
    }

This should run in O(n log(n))