Little problem(s) July 2022

[pier4r]

(07-07-2022 12:02 PM)DavidM Wrote:  

(07-07-2022 10:51 AM)pier4r Wrote:  (I hope GET is O(1) with lists in userRPL, now I start to have doubts).

It isn't with lists, but it is with type 3 or 4 arrays.

Remember that lists can contain many different types of objects as elements (even other lists), so the size of each element may vary and cannot be assumed in advance. Lists have no associated metadata (pointers, tables, etc.) that would assist in locating specific elements. The only way to locate element n is to sequentially step through elements 1..(n-1) first.

Somehow I forgot (or I wanted to forget) this part. So even GET is O(n) ? Brutal, but that is the limit of small machines and arbitrary data in lists.