Коллеги, подскажите, какова сложность вставки в обычную таблицу? Декларация такая:
DATA t_x type table of X.
Ну и insert ... index z.

Какова организация обычных массивов в сапике? paging есть?

Ну если верить вот этому, то

Т.е. можно предположить, что сложность O(1)
Под paging вы что имеет ввиду?

С access то все понятно. Интересует insert. В худшем случае (таблица есть обычный массив в памяти) - стоимость вставки = O(N).
paging, наверное, некорректно выразился, имел ввиду нечто типа страниц в СУБД - тогда вставка O(1).

Таблица - не обычный массив. Насколько я помню - строка добавляется куда получится (в конец массива, например), а вся работа идет с индексом. Так что стоимость вставки для таблицы как для массива O(1), стоимость вставки для индекса O(N), как рассчитать стоимость вставки в целом - я без понятия

P.S. вам для чего, если не секрет?

Ну в целом сложность тогда O(N), конечно, хотя видимым это должно стать только при весьма больших N. Спасибо за информацию!

Интересуюсь скорее больше теоретически. Вопрос вылез из более частного - что быстрее:

SORT xxx BY yyy.
DELETE ADJ DUP from xxx COMP BY yyy.

или цикл по xxx и COLLECT в другую таблицу.

Учитывая информацию, которую вы написали - теоретически первый подход быстрее. O(N * log(N)) vs O(N^2) соответственно (COLLECT предполагается в стандартную таблицу, не хэш и не сортированная. С хэшем, конечно, O(N), но это другая задача ).

Эммм.. на больших размерах внутр.таблицы это будет сильно зависеть от. Память под внутр. таблицу не выделяется "построчно", она выделяется блоками (ага-ага - page). Причем сперва блоки 8кб. Далее - блоки в зависимости от размера строки-8-16кб. Поэтому и стоит рекомендация: если вы даже ожидаете в табле немного записей - ставьте адекватный INITIAL SIZE при ее объявлении (чтобы все было в пределах одной page).
При использовании collect, у вас будет 2 таблицы вместо одной (съедаем больше памяти, которая тоже будет разложена по своим page). Но с др. стороны, если collect у вас происходит в станд.таблицу и больше никаких действий вы над ней не выполняете(insert\delete\modify), то интерпретатор будет выполнять ее с использованием temporary hash administration.
Внутри реализовано много всяких оптимизаций, поэтому четкого ответа по сложности видимо нет. Общее представление об устройстве можно получить в книге sappress ABAP Performance Tuning