Logical difference between LINQ Where() and FirstOrDefault()

Question

I know this may sound duplicate question (like this or this ) but I wanted some clarity regarding the number iterations that will take place in this query.

My assumptions are as follows:

lets say I have collection of 1000 items.

In Where() query, it iterates through each and every item and add it to IEnumerable. i.e. it will need O(n) always.

foreach (var item in myList)
{
    if(//<condition>)
    {
        //add it to list/enumerable
    }
    //continue through entire list
}

In FirstOrDefault(<condition>) query,it starts iterating through the collection and breaks the loop as soon as it gets the item matching the <condition> and returns single element or only if no item is matching <condition> then it will iterate through entire list.

so complexity can be from O(1) to O(n)

foreach (var item in myList)
{
    if(//<condition>)
    {
        //return item
        break;
    }
}

if this is correct then it will always be better to use FirstORDefault for a single item return.?

Big-O is expressed as the worst case scenario. `FirstOrDefault()` will be 0(n). — Jeroen Vannevel, Nov 18 '13 at 15:39
For a single item return, you should use `FirstOrDefault` (or similar methods, e.g. `Single`), not `Where`, because that's what it best expresses. Whether it's faster than some other implementation is another question. — Tim S., Nov 18 '13 at 15:43

score 15 · Accepted Answer · answered Nov 18 '13 at 15:37

15

Where is actually deferred - i.e. it does not have any cost until the enumeration happens.

Where looks kind of like this, and returns a new IEnumerable<T>.

foreach (var item in enumerable)
{
    if (condition)
    {
        yield return item;
    }
}

FirstOrDefault returns T.

answered Nov 18 '13 at 15:37

Daniel A. White

187,200
47
362
445

Wow.I didn't know this deferred thing. Thanks for clearing doubt. – deathrace Nov 18 '13 at 15:42
1

@deathrace when you see a standard linq operation return `IEnumerable` (or one of its derived forms), it is a deferred result. – Daniel A. White Nov 18 '13 at 15:43
@DanielA.White What would be better approach if we are dealing with IQueryable, I assume that `Where()` would be a good option as it will apply filter on datasource. Is it correct? – Muhammad Ummar Aug 04 '15 at 10:59
@Ummar it depends on the query provider. – Daniel A. White Aug 04 '15 at 14:30
@DanielA.White I am working in LINQ to SQL. any idea about its internal working? – Muhammad Ummar Aug 07 '15 at 07:58

score 2 · Answer 2 · answered Nov 18 '13 at 15:38

2

FirstOrDefault will stop checking (i.e. break) when/if it finds anything.

edit: However, as Daniel pointed out, Where is deferred, so you can also stop iterating yourself and it will have the same performance as FirstOrDefault (although then you might as well just use FirstOrDefault)

answered Nov 18 '13 at 15:38

David S.

5,965
2
40
77

The point of the question is the OP thinks that `Where()` will fully enumerate the list before passed on to `FirstOrDefault`. Which means his assumption is incorrect, not correct. – Scott Chamberlain Nov 18 '13 at 15:40

score 2 · Answer 3 · answered Nov 18 '13 at 15:44

2

FirstOrDefault enumerates the query while Where just returns a new enumerator. Below statements give the same results:

var result = coll.FirstOrDefault(predicate);
var result = coll.Where(predicate).FirstOrDefault();

answered Nov 18 '13 at 15:44

tukaef

9,074
4
29
45

If I want to find the result then which one is better? – Mir Gulam Sarwar Nov 17 '17 at 04:34

Logical difference between LINQ Where() and FirstOrDefault()

3 Answers3

Linked

Related