Little problem(s) July 2022

[Albert Chan]

(07-05-2022 01:56 PM)pier4r Wrote:  Why is POS \(\mathcal{O}(n)\) in userRPL? Is there no direct access to the position in a list, does the system have to iterate through the elements every time? (is DOSUBS the only way to avoid it?)

POS first need to match the object, then return its position.
With unsorted list, linear search is O(n)
Sorted list can use binary search, time complexity O(log(n))

BTW, if the list were sorted, there is no need for POS at all.
We just repeatedly shorten the 2 tails ...

Code:

function f2(lst, x) -- lst sorted, no duplicates
    local i, j = 1, #lst
    while i < j do
        local y = lst[i] + lst[j] - x
        if     y > 0 then j=j-1
        elseif y < 0 then i=i+1
        else print(i, j); i=i+1; j=j-1
        end
    end
end

lua> f2({2,7,11,15}, 17)
1      4
lua> f2({2,5,7,8,10,11,15}, 15)
2      5
3      4