Little problem(s) July 2022

[Thomas Klemm]

(07-05-2022 01:56 PM)pier4r Wrote:  Why is POS \(\mathcal{O}(n)\) in userRPL?

I must admit that I don't know the details, but I assume that POS has to check every entry to find the position.
The worst case is if we search for an entry that is absent.

This program measures the time of POS for an increasing list:

Code:

\<< 1 SWAP
  FOR i
    DUP + DUP
    TICKS
    SWAP 0 POS DROP
    TICKS SWAP -
    SWAP
  NEXT
  DROP
\>>

Example

{ 1 1 1 1 1 1 1 1 }
10

This produced the following values:

8 14 29 74 93 181 245 343 430 580

It looks like an exponential curve to me:



Since the length of the list is doubled in each iteration this gives a linear relationship.
At least it is not logarithmic and definitely not constant.