12

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?

10
  • 3
    It would be interesting to compare the IL produced by the compiler for each of these. May 18 '15 at 17:48
  • @DanPichelman - Quit nerd-sniping me! Yes, I agree that would be interesting to find out. Are they equivalent or not?
    – user53019
    May 18 '15 at 17:49
  • Might it save some time to loop over bars and filter on bar.PropZ.HasValue first, if you expect more than a tiny amount to evaluate to false? Doesn't really answer your question, I am just reviewing your code.
    – user22815
    May 18 '15 at 17:50
  • 1
    Are these two loops even doing the same thing, particularly in the case where foo.PropA == bar.PropA is true for multiple entries in barList? Edit: definitively not as the second one will throw a NullReferenceException when the select returns null. May 18 '15 at 17:53
  • 1
    I would guess that .FirstOrDefault() will make the linq loop exit early if a match is found, while your dumb nested loops do not exit early, so yes, I would think that linq will have a better big-oh. But I am not sure, hence a comment and not an answer.
    – Mike Nakis
    May 18 '15 at 17:56
16

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.)

2
  • "the linq-based solution is faster" Who knows? LINQ has constant-factor overhead that can easily exceed 2x.
    – usr
    May 21 '15 at 21:05
  • @usr: You are right, it depends on the frequency of matches rather than the size of the lists. The higher the frequency of matches, the bigger relative advantage of the linq-based solution.
    – JacquesB
    May 22 '15 at 12:57
5

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))

1
  • Could you explain why it would run O(n log(n))? Following the source code, it seems to create a Lookup(Of TKey, TElement), iterate over barList, get the Grouping for each item, and adds items to the Grouping. It then iterates over fooList, gets the Grouping, and returns each element in the grouping. Where does the `log(n) come from? Jan 12 '17 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy