4 ms·
It's fun to think about: you have a structure which allows you to iterate all elements in order in O(n) time. Isn't this in many ways equivalent to the structur
by krajzeg 7y ago
It's fun to think about: you have a structure which allows you to iterate all elements in order in O(n) time. Isn't this in many ways equivalent to the structure being "sorted", even if it doesn't have all the properties of a sorted array (like being able to get the nth element in O(1))?
For example, a sorted linked list behaves almost exactly like this spaghetti column.
- s_gourichon 7y agoInteresting remark. So, a "data structure where the largest remaining element can be extracted in O(1) time" can be turned into a sorted list in O(n) time. So, under the assumtions, the overall algorithm does complete in constant time.