Сложность выполнения IEnumerable.First() с предикатом равна O(n)?

В сети есть статьи, где обсуждаются алгоритмические сложности различных команд LINQ, но что-то ничего про сложность IEnumerable.First() с предикатом я не смог найти. Она ведь равна O(n)?