Bei allem was ICollection<T> implementiert über die Count-Eigenschaft -> ist ein O(1) Vorgang mit nur einem Befehl.

Für die Any-Erweiterungsmethode sind mehr Schritte nötig die unnötig sind ;) Diese Methode hat folgenden Code (ist im Prinzip auch O(1) aber aufwändiger):

public static bool Any<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
        throw Error.ArgumentNull("source");

    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        if (enumerator.MoveNext())
            return true;

    return false;
}

Der Unterschied wird meist vernachlässigbar klein sind und daher ist es egal. Was nicht verwendet werden sollte ist in diesem Fall die Count-Erweiterungsmethode denn diese würde über die ganze Enumeration iterieren (es sei denn es ist eine ICollection<T>) und das ist bei großen Listen unnötiger Aufwand ;)