Я правильно понимаю, что в рефале невозможно сделать доступ к произвольному элементу за O(1), что в лучшем случае только за O(ln(n))?

В Рефале данные хранятся не в массиве, а в структуре-разновидности дерева.
Вообще это может от реализации зависеть.

Идиомы программирования на Рефале -- там упоминаются массивы и прочие структуры данных.

Парадигма -- это хорошо, но сложность она объективна, и некоторые алгоритмы таки требуют произвольного доступа.

Полистайте на досуге Purely Functional Data Structures
При использовании ленивого чистого ФП сложность алгоритмов может быть другой.

Кстати, а при чем тут рефал?

[Кроме того, "аммортизационная сложность" очень сильно напоминает некий маркетоидный приём

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, because the rest of the insertions are done in constant time, so n insertions can be completed in O(n) time. The amortized time per operation is therefore O(n) / n = O(1).

Ну Вы же сами написали, что хотите убедиться, что ничего не упускаете.
Рефал -- язык чистый, интересно, имеет ли значение, лениво или энергично там устроены вычисления?

А с какой именно реализацией Рефала Вы занимаетесь?

Крупная неудача. Если мозги есть, то обратит внимание. И начнет копать. А если не обратит - туда ему и дорога...

Я знаю что там не массив, а двусвязный список. "скобочки" это нечто не с двумя ссылками, а с тремя (предыдущий, следующий, ссылка на парную скобку).

Предлагаю когнитивности эти отделить в отдельную тему, ибо к центральной теме обсуждения (Рефал) это НИКАКОГО отношения не имеет. В каком нибудь разделе по психологии и педагогике обсуждайте.

Ну да, в пятом вроде - двусвязанный список. Что совершенно не догма, как и отмечено по приведенной Вами сслылке...

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

Скажем так: ассимптотика функции <First s.N e.Expr> - шибко зависит от реализации. В пятом - O(N) почти наверняка. В плюсе - O(1) скорее всего.

Почему же.
В моем первом сообщении в этой подветочке было указано на ошибку, совершенную в отношении именно Рефала.
Хотя корни ошибки -- в общей "когнитивности".
А также в не-до-конца-понимании всего значения понятия "парадигма" применительно к императивной, функциональной и прочим парадигмам программирования.

Вопрос абсолютно чисто технический. ...

Так это всегда так.

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

некоторые алгоритмы таки требуют произвольного доступа