Equivalent data structures with the same boundaries in the worst case (compared to amortized ones)

Question

I could not make my headline very descriptive, apologies!

Is it so that for each data structure that supports certain operations with a specific depreciation time, another data structure that supports the same operations at the same time in the worst case? I am interested in iterative, ermal data structures and functional ones.

I am sure this question must have been asked before. I can not find the right keywords to search (in Google, SO, TCS). I am looking for a quoted answer in {yes, no, open}.

Answer 1

No, at least in models where the elementality of cells for n elements requires time Ω (n log n).

Consider the following data structure, which I am describing with Python.

class SpecialList: def __init__(self): self.lst = [] def append(self, x): self.lst.append(x) def rotationalsimilarity(self, k): rotatedlst = self.lst[k:] + self.lst[:k] count = sum(1 if x == y else 0 for (x, y) in zip(self.lst, rotatedlst)) self.lst = [] return count 

It is clear that append and rotationalsimilarity (since it clears the list) are depreciated by O (1). If rotationalsimilarity were the worst O (1), then we could provide an O (1) undo operation that restores the data structure to its previous state. It follows from this that we could realize the elementality in time O (n).

 def distinct(lst): slst = SpecialList() for x in lst: slst.append(x) for k in range(1, len(lst)): # 1 <= k < len(lst) if slst.rotationalsimilarity(k) > 0: return False slst.undo() else: return True