Performance of SortedList.Last with predicate

Question

I would like to find the value of the last item in a SortedList that is under a certain value. Since SortedList is implemented with something capable of binary searches, this is possible in O(log(n)).

What will the performance of this code be:

data.Last(x => x.Key < 100);

I can only find documentation for Enumerable.Last ( http://msdn.microsoft.com/en-us/library/bb549138(v=vs.90).aspx ) and I want to make sure it doesn't use a generic enumerator-based implementation.

Answer 1

A SortedList performs the same as any IEnumerable<T> for .Last method, both are O(n);

Answer 2

I'll answer your question with another question. How would SortedList utilize its inherent sorting to do better than O(n) for any arbitrary predicate?

Unless you make assumptions about the predicate you essentially have to use a standard enumerator approach