Алгоритмическая сложность операций с NSMutableArray

В оффициальной документации подобного нет (в явном виде), что и следовало ожидать.

Но почитав детально, стает понятно, что ничего нового изобрести в Эппл не могли, и скорее всего там следующее.

а) вставка нового элемента в начало структуры;

в этом случае нужно выделить место под новый элемент, скопировать все элементы, сдвинув индексы на 1 и вставить новый элемент. Перемещение элементов имеет сложность O(n). Выделение памяти обычно константное, если размеры небольшие. При больших размерах (десятках и сотнях мегабайт) сложность нужно рассматривать отдельно. Поэтому, на небольших объемах массива вставка нового элемента в начало - это O(n). На большом размере массива нужно смотреть в менеджер памяти.

б) вставка нового элемента в конец структуры;

в академическом смысле эта задача сводиться к выделению нового объема памяти переносу всех элементов и вписыванию в конец нового элемента. То есть, по факту, ничем не отличается от предыдущей. Но тут научились делать одну оптимизацию. Памяти выделяют немного больше, чем нужно и в результате выделения памяти (и копирование всего массива) происходит не часто. Если копирование не происходит, то сложность добавления в конец - O(1). Документация косвенно подтверждает, что память выделяется с запасом.

в) поиск существующего элемента по значению;

здесь документация однозначно говорит, что сложность O(n) - пробегают по всему списку элементов, пока не найдут нужный.

г) поиск существующего элемента по индексу;

здесь обычно, если ничего не постарались сделать, то сложность константная, O(1), потому что просто нужно умножить индекс на размер элемента и приплюсовать начало массива.

д) удаление существующего элемента.

здесь все то же самое, что и при добавлении элементов. Единственно, что память никто не уменьшает.