What guarantees are there on the run-time complexity (Big-O) of LINQ methods?

by

There are very, very few guarantees, but there are a few optimizations:

  • Extension methods that use indexed access, such as ElementAt, Skip, Last or LastOrDefault, will check to see whether or not the underlying type implements IList<T>, so that you get O(1) access instead of O(N).

  • The Count method checks for an ICollection implementation, so that this operation is O(1) instead of O(N).

  • Distinct, GroupBy Join, and I believe also the set-aggregation methods (Union, Intersect and Except) use hashing, so they should be close to O(N) instead of O(N²).

  • Contains checks for an ICollection implementation, so it may be O(1) if the underlying collection is also O(1), such as a HashSet<T>, but this is depends on the actual data structure and is not guaranteed. Hash sets override the Contains method, that’s why they are O(1).

  • OrderBy methods use a stable quicksort, so they’re O(N log N) average case.

I think that covers most if not all of the built-in extension methods. There really are very few performance guarantees; Linq itself will try to take advantage of efficient data structures but it isn’t a free pass to write potentially inefficient code.

More Related Contents:

  1. C# custom add in a List
  2. Group By Multiple Columns
  3. LINQ query on a DataTable
  4. Distinct not working with LINQ to Objects
  5. When to use Cast() and Oftype() in Linq
  6. How to get index using LINQ? [duplicate]
  7. How do I concatenate two arrays in C#?
  8. Split a collection into `n` parts with LINQ? [duplicate]
  9. Order of LINQ extension methods does not affect performance?
  10. Algorithm for simplifying decimal to fractions
  11. Query an XDocument for elements by name at any depth
  12. What is the point of Lookup?
  13. Nice & universal way to convert List of items to Tree
  14. Am I misunderstanding LINQ to SQL .AsEnumerable()?
  15. How Math.Pow (and so on) actually works
  16. Enumerating through an object’s properties (string) in C#
  17. Is the Linq Count() faster or slower than List.Count or Array.Length?
  18. Intersect LINQ query
  19. LINQ – Query syntax vs method chains & lambda [closed]
  20. Resolving extension methods/LINQ ambiguity
  21. Max or Default?
  22. What does this C# code with an “arrow” (=>, an equal sign and greater than sign) mean and how is it called?
  23. Using Linq Except not Working as I Thought
  24. What is the purpose of AsQueryable()?
  25. How do I do a left outer join with Dynamic Linq?
  26. LINQ query to return a Dictionary
  27. LINQ performance FAQ
  28. A dictionary where value is an anonymous type in C#
  29. How to convert DataTable to class Object?
  30. How do I compose Linq Expressions? ie Func

Leave a Comment