Is string.ElementAt() O(1)?

Question

Under remarks, it says

If the type of source implements IList, that implementation is used to obtain the element at the specified index. Otherwise, this method obtains the specified element.

String does not implement IList<T>. Does that mean this will be an O(n) operation if I declare something like,

IEnumerable<char> myString = "stringy";

?

Answer 1

ElementAt when applied to a type which is a string will be an O(N) operation. It does not implement IList<char> and hence ElementAt won't do any optimizations on it and instead enumerates through the IEnumerable<char> until it reaches the specified index.

Answer 2

Since string is not implementing IList but IEnumerable<char> ElementAt will execute the following code:

using (IEnumerator<TSource> enumerator = source.GetEnumerator())

and GetEnumerator on string retrieves a CharEnumerator which is O(n) as you assumed.

If you want a better implementation create your own extension method

public static class StringExt
{
    public static char ElementAt(this string input, int index)
    {
        if (index < input.Length) return input[index];
        throw new IndexOutOfRangeException();
    }
}

which I assume is O(1), but hard to tell since the index accessor on string is done in unsafe code.