Any() Time Complexity

Question

I believe the answer to this question is well explained here:LINQ Ring: Any() vs Contains() for Huge Collections

But my question is specific for the current implementation

IEnumerable<T> msgs = null;

/// ...
/// some method calls which returns a long list of messages
/// The return type of the method is IEnumerable<T>
/// List<T> ret = new List<T>();
/// ...
/// return ret
/// ...
if (msgs.Any())
    object= msgs.Last();

The msgs is an in memory collection (IEnumerable) said. 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?

Answer 1

I assume that IEnumerable<BaseJournalMessage> msgs is not a collection like an array or list, otherwise the Any and Last would be no problem(but you have performance issues). So it seems to be an expensive LINQ query which gets executed twice, once at Any and again at Last.

Any needs to enumerate the sequence to see if there is at least one. Last needs to enumerate it fully to get the last one. You can make it more efficient in this way:

BaseJournalMessage last = msgs.LastOrDefault();
if (last != null)
    time = last.JournalTime;

To explain a bit more. Consider msg was an array:

IEnumerable<BaseJournalMessage> msgs = new BaseJournalMessage[0];

Here Any is simple and efficient since it just needs to check if the enumerator from the array has one element, same with other collections. The complexity is O(1).

Now consider that it's a complex query, like it seems to be in your case. Here the complexity of a following Any is clearly not O(1).:

 IEnumerable<BaseJournalMessage> msgs = hugeMessageList
    .Where(msg => ComplexMethod(msg) && OtherComplexCondition(msg))
    .OrderBy(msg => msg.SomeProperty);

This is not a collection since you don't append ToList/ToArray/ToHashSet. Instead it's a deferred executed LINQ query. You will execute it every time it will be enumerated. That could be a foreach-loop, an Any or Last call or any other method that enumerates it. Sometimes it's useful to always get the currrent state, but normally you should materialize the query to a collection if you have to access it multiple times. So append ToList and everything's fine.

Have a look at the term "deferred execution" in each LINQ method(as for example Where, Select or OrderBy) if you want to know whether it's executing a query or not. You can chain as many deferred executed methods as you want without actually executing the query. But if a method contain "forces immediate query evaluation"(like for example ToList) the query gets executed(so avoid those methods in a middle of a query).

Answer 2

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?

As for LinQ-To-Object, implemented in System.Linq.Enumerable static class, the implementation of Any() just gets the IEnumerator and invokes MoveNext(). If the result is true, Any() returns true itself. Otherwise it returns false. It never iterates any further.

So it is a pure O(1) algorithm. EDIT: I have to correct myself: The time depends on the enumerable "Any" iterates. I had a misconception of the Big O notation and the meaning of "O(1)" and "O(n)".

This is the source code (source available at GitHub these days):

    public static bool Any<TSource>(this IEnumerable<TSource> source) {
        if (source == null) throw Error.ArgumentNull("source");
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            if (e.MoveNext()) return true;
        }
        return false;
    }