This isn't true. Once you have tens of thousands of records, a poorly written algorithm or data structure is going to lead to O(n^2) behavior. That hurts. Even small sites can hit this amount of database records with ease.