Big-O of ReadOnlyCollection<T>.Last?

Folks,

What's the Big-O of ReadOnlyCollection<T>.Last (Linq extension method)?
I'm hoping o(1), but I can't tell from the documentation.

It seems the linq extension is on IEnumerable...but perhaps it leverages the underlying IList for faster access?  I have no clue.
LVL 1
sfun28Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

abelCommented:
As you maybe well aware of, the ReadOnlyCollection is not nothing more then a wrapper around an IList (which you have to give with the constructor). All its operations are performed on this underlying datatype.

But.... the Last method is actually a static extension function (all ext. functions are static), which is part of System.Linq.Enumerable.

But... and now it gets tricky...: the Enumerable.Last method has a signature as follows:

  public static TSource Last<TSource>(this IEnumerable<TSource> source)
meaning that it is an extension function to anything that implements IEnumerable. So far from the documentation. Now let's have a look at the implementation. As it appears, the Enumerable knows about the IList interface and the first thing it tries is to cast the IEnumerable to an IList. If it succeeds, it returns (simplified) the following:

IList<TSource> list = source as IList<TSource>;return list[list.Count -1]
That is indeed an O(1) operation and actually, it's the answer to your question since the ReadoOnlyCollection must use an underlying IList type. But let's take it a tad further to see what happens if the IEnumerable does not also derive from IList. In that case, the method cannot do anything else then looping through all the until the end. This is O(n) performance and not really efficient. Luckily, most collection types, including System.Array (of which all array types derive) implement the IList interface and as a result, the performance of Last() is instantaneous: O(1). (I'm not certain whether the same holds for Mono's implementation).

For completeness, here's the reference that I used to look this up with Reflector:

public static TSource Last<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    IList<TSource> list = source as IList<TSource>;
    if (list != null)
    {
        int count = list.Count;
        if (count > 0)
        {
            return list[count - 1];
        }
    }
    else
    {
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            if (enumerator.MoveNext())
            {
                TSource current;
                do
                {
                    current = enumerator.Current;
                }
                while (enumerator.MoveNext());
                return current;
            }
        }
    }
    throw Error.NoElements();
}
 
 
 
 

Open in new window

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
sfun28Author Commented:
Wow!!!  Thanks so much!  This was one of the most complete answers I've ever gotten.  Great idea to examine this in reflector...I wouldn't have thought about that.
0
abelCommented:
compliments like that should be in the open, don't you think? if you don't mind, I copy it here so others can see it too (yes, I know, I'm egocentric! lol ;-)

(from grading comment)
Wow!!! Thanks so much! This was one of the most complete answers I've ever gotten. Great idea to examine this in reflector...I wouldn't have thought about that.
Tx for the great compliment and glad to have been of help! :)
0
C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

sfun28Author Commented:
Out of curiosity, is the code reference something you just copied/pasted from reflector?
0
abelCommented:
Yes, I just pasted that from Reflector, nothing of it is my own. That also means, that the code is not exactly the same as the Shared Source Code from Microsoft that you get into when you are debugging. But the Shared Source Code is protected by copyright law, but reflected assembly is not.

There is a small mishap in my story. It doesn't change anything, but the story above might be understood as that IList and IList<T> are the same. System.Array implements IList and ReadOnlyCollection implements both IList<T> and IList. For the functionality in the code above this doesn't make any difference as an Array / IList can be cast to IList<T>.

-- Abel --


0
sfun28Author Commented:
Thanks!!!  Great explanation!
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
.NET Programming

From novice to tech pro — start learning today.