Are there any cases where LINQ's .Where() will be faster than O(N)?

Question

Think the title describes my thoughts pretty well :)

I've seen a lot of people lately that swear to LINQ, and while I also believe it's awesome, I also think you shouldn't be confused about the fact that on most (all?) IEnumerable types, it's performance is not that great. Am I wrong in thinking this? Especially queries where you nest Where()'s on large datasets?

Sorry if this question is a bit vague, I just want to confirm my thoughts in that you should be "cautious" when using LINQ.

[EDIT] Just to clarify - I'm thinking in terms of Linq to Objects here :)

Answer 1

It depends on the provider. For Linq to Objects, it's going to be O(n), but for Linq to SQL or Entities it might ultimately use indices to beat that. For Objects, if you need the functionality of Where, you're probably going to need O(n) anyway. Linq will almost certainly have a bigger constant, largely due to the function calls.