title: In-memory LINQ performance
body: <p>More than about LINQ to [insert your favorite provider here], this question is about searching or filtering in-memory collections. </p>
  
  <p>I know LINQ (or searching/filtering extension methods) works in objects implementing <code>IEnumerable</code> or <code>IEnumerable&lt;T&gt;</code>. The question is: <em>because of the nature of enumeration, is every query complexity at least <strong>O(n)</strong>?</em></p>
  
  <p>For example:</p>
  
  <pre><code>var result = list.FirstOrDefault(o =&gt; o.something &gt; n);
  </code></pre>
  
  <p>In this case, every algorithm will take at least <strong>O(n)</strong> unless <code>list</code> is ordered with respect to <code>'something'</code>, in which case the search should take <strong>O(log(n))</strong>: it should be a binary search. However, If I understand correctly, this query will be resolved through enumeration, so it should take <strong>O(n)</strong>, even in <code>list</code> was previously ordered.</p>
  
  <ul>
  <li>Is there something I can do to solve a query in <strong>O(log(n))</strong>?</li>
  <li>If I want performance, should I use Array.Sort and Array.BinarySearch?</li>
  </ul>