Какова сложность выполнения запроса со вложенным Length (строки) в LINQ

Есть задача, нужно найти наиболее длинное слово из этого списка, а из наиболее длинных — лексикографически первое слово. В метод передаётся коллекция, нужно вернуть одно слово. В одну операцию, без использования сортировок, сложность должна быть не более O(N).

Вроде бы всё легко, однако ограничение по сложности уменьшает варианты ответов и здесь появляются вопросы. Самое близкое по простоте и скорости решение, с которым я смог определиться:

public static string GetLongest(IEnumerable<string> words)
{
    return words
        .Min(word => Tuple.Create(-word.Length, word)).Item2;
}

Ответ с одной стороны правильный, однако проблема в Length и LINQ, на сайте нет проверки по сложности. Все варианты решения, которые я смог придумать и найти(в т.ч. от других учеников) - с использованием свойства Length у строк. Я знаю, что само по себе свойство у строк имеет сложность O(1), Min() от LINQ O(N), однако человек в комментариях мне пояснил, что: "механизмы LINQ сначала пройдутся циклом по всей коллекции и извлекут все значения Length и потом будут запускать механизмы сортировок, поиска max/min и т.д. То есть в лучшем случае общая сложность запроса будет не проще чем O(N * log(N)).".

Соответственно, интересно насколько это правда, и каким способом возможно решить за O(N), если он прав. Интересна даже больше сложность данной операции, чем правильное решение.