When designing a data structure, should I implement very inefficient operations for convenience?

(I've added the .NET tags because the data structures are for .NET, and this question should be considered in the context of the conventions for that platform.)

I'm writing a library of immutable and persistent data structures for .NET. One of my data structures, a type of vector, supports the following core operations:

1. Addition and removal at the end


2. Lookup and update by index


3. Starting subsequence


4. (Uninteresting things like length, etc)

In addition, there is a special implementation of bulk operations (involving sequences, such as addition of many elements) that is extremely fast for large inputs. This makes addition of many elements to the end very, very fast.

My issue is a bit more complicated than the title of the question makes out. I can implement the following additional operations:

1. Addition of many elements at the beginning


2. Insertion of many elements in the middle

Addition of many elements to the end is O(m + logn), where m is the number of elements to be added. These operations would be O(n + m), and if m = n then they are almost as fast as addition to the end. In practice, they would be many orders of magnitude faster than if the user implemented them naively. However, for small numbers of elements, they would still be very slow.

My first problem is that the normal operations are so fast, they might confuse users and make them think these additional operations perform in a similar manner. Unlike for regular collections where even List<T>.Insert is fast, this can actually bottleneck the application. How should I deal with this?

My second problem is that, if I implement these additional operations, should I also provide similar (extremely inefficient) operations that work with single elements? It seems strange not to provide these apparently simpler operations, and I'm sure they will be handy (performance isn't important at all sometimes), but that surprise factor is even worse here, since these operations can never be efficient.

A similar consideration applies for a Skip (ending subsequence) operation.