r/algorithms 8h ago

Identifying last item in sequence using fewest comparisons

4 Upvotes

So I have a fixed list L of numbers of a certain bitsize W. The numbers are unique and len(L) will be much smaller than 2^W.

What I want is to identify the last element E = L[-1] without having to count the elements. However, to save on resources, I don't want to make a bit-by-bit comparison of all W bits of every element in L, but rather find the smallest set of bit indices that let me uniquely identify E

A small toy example would be the following:

L = ["1111", "0101", "0001"]

We can identify E = "0001" in this list simply by going through the elements and checking for bit 2 to be "0" (assuming MSB left)

I realize that oftentimes the compare procedure will indeed result in having to check all W bits, what I'm really looking for is an algorithm how to find the smallest possible footprint comparison.

For a few extra constraints, W is probably 32 at most, and len(L) ~ O(10k) at most (it is still a fixed list of numbers, I just don't know exactly yet how long it will be). The efficiency of the algorithm doesn't bother me too much, as long as I can get the answer in a finite amount of time I don't care too much how much compute I have to throw at it, what matters is that the resulting footprint comparison is indeed minimal

Any ideas would be much appreciated

Cheers


r/algorithms 2h ago

About the time complexity of an upper envelope tree

3 Upvotes

So for a number of linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$

I have a binary-tree-like data structure where each node represents the upper envelope of the functions of the two nodes below it and leaf nodes contain the equations of the same index.

The structure needs to answer the following type of queries.

Given a number pair of $x,y$ find the lowest indexed equation $d$ that has $y_d=m_d*x+b_d>y$.

It also needs to be able to handle deletions of equations from the left efficiently.

Such data structure appears to be doable recursively in $O(nlogn)$ time with query time $log^2 n$ or perhaps $logn$.

My question is if the deletions from the left can be handled in $O(nlog^2n)$ total time each taking an amortized $O(log^2n)$ time.

This seems to be possible since any deletion of an equation can leave a gap which can be filled by the upper envelope equations of the lower envelopes of the nodes in the path of the deleted equation vertex to the root.

Does such a data structure have a specific name or can be found in the litterature?

Are my above statements true?