0

I thought this should be a common question that already got answered elsewhere, but I couldn't find any resources explaining the time complexity of C# Linq method. Hopefully I'm not posting a duplicated question here.

Recently I noticed some performance issue of my company's product and eventually figured out that the Any() method is taking a long time to process over the time of the software has been running. So I started to look into the time complexity of this method. But I didn't find any document or resource to explain it, or for any other Linq method. But my current suspect is that Any()'s time complexity is O(n). I'm also curious about other Linq methods' time complexity as well.

It will be great if someone familiar with Linq can point me to a resource/document to look at this. Any help will be really appreciated.

Thank you very much.

Weilun Yuan
  • 41
  • 1
  • 9
  • 3
    [Related](https://stackoverflow.com/q/2799427/1997232). And specifically to `Any()` see [this topic](https://stackoverflow.com/q/4445219/1997232). – Sinatr Jul 09 '21 at 14:47
  • 3
    Can you confirm if it is running linq against an in memory collection (IEnumerable) or against an external source (IQueryable)? If IQueryable the the complexity will be dependant on the query provider's implementation – Alex Jul 09 '21 at 14:51
  • It's not really a useful analysis. The _performance_ of Any() depends on the data and the provider. If there are none and the provider is not using an index, then it will have to examine them all, but if say the data is 50:50 and it does have to do a scan, it's very likely to terminate quickly (0.5+0.25+...) and the size of N makes very little difference. – Ian Mercer Jul 09 '21 at 14:54
  • 4
    I would suspect it is dependent on the provider. While it may be O(n) at one place might be O(1) in another. In Linq To SQL for example it resolves to an EXISTS query, makes me believe it is O(1). – Cetin Basoz Jul 09 '21 at 14:54
  • 1
    @IanMercer: but the time complexity it still O(n) if you have to enumerate all in worst case – Tim Schmelter Jul 09 '21 at 14:56
  • @TimSchmelter which is interesting to academics but the OP has a _performance_ issue. – Ian Mercer Jul 09 '21 at 14:57
  • 1
    @IanMercer: this question is academic since it asks many in one without showing the actual code. So we can just answer academically – Tim Schmelter Jul 09 '21 at 14:58
  • The original code looks like this: if (msgs.Any()) time= msgs.Last().JournalTime; The msgs is an in memory collection as Alex said. Maybe this is a stupid question, but how does Any() work here? There's no condition for this Any() method call, isn't it just O(1) instead? Or it still looks through each element? – Weilun Yuan Jul 09 '21 at 15:01
  • 1
    @WeilunYuan: Maybe you want to ask a new question and add your code there. Otherwise you had to change almost everything in this. – Tim Schmelter Jul 09 '21 at 15:02
  • @TimSchmelter Got it, thank you! – Weilun Yuan Jul 09 '21 at 15:03
  • Any without a predicate is extremely quick (in Linq-2-objects) and has an algorithm of O(1). With a predicate it's O(1) to O(n); – lidqy Jul 09 '21 at 15:05
  • @lidqy: even in Linq-To-Objects an Any without predicate can take an eternity to execute since it depends entirely on the type of the `IEnumerable`. It could be a collection, then it's indeed an O(1) operation(because of the `Count`-property) or it could be an expensive query that finishes tomorrow or never. What makes it O(n) is the fact that it depends on the size in that case. – Tim Schmelter Jul 09 '21 at 15:47
  • @TimSchmelter if it is an enumerable that does not support ICollection, i.,e. has no `Count` property, `Any` without a condition/predicate will still just need one iteration (technically one invocation of `IEnumerator.MoveNext()` with return value of `true`) and then Any will break the iteration and return true. Okay it might be the case that simply querying the collection is a long process. But without a condition the iterator has just to proof that there is at least 1 element contained - and that is an pure O(1) algorithm or even close to O(0) if `Count` is available. – lidqy Jul 09 '21 at 17:52
  • Any() without a condition has O(1) algorithm, with a predicate it#s O(n). **BUT**: Any can still cause a IEnumerable, that is Linq-Query, to be executed. And this can be very time-consuming. – lidqy Jul 10 '21 at 01:30
  • Example: `var data = myColl.Where (a =>A a.IsBig(100)).SelectMany(a => a.InnerList).GroupBy(a => a.DataKey);` `if (data.Any())` Here Any() will cause the previous query named `data` to be executed. Hint: **deferred execution** https://www.google.com/search?q=linq+deferred+execution – lidqy Jul 10 '21 at 01:34

0 Answers0