Search code examples
c#.netperformancebinary-searchsortedlist

Performance of SortedList.Last with predicate

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.

Solution

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