Re:Exotic Data Structures (2011)
by mnarayan01 on Tuesday July 11, 2017 @09:38AM
(#14744047)
Where are you getting O(sqrt(n)) space from? The linked article says O(n) for compact dynamic arrays.
[ Parent
| on HN ]
Note that the original article describes space complexity as "N + O(sqrt N)", i.e., there are N records and O(sqrt N) extra space.
Their data structure is considerably more complex than traditional implementations of std::deque, I wonder if it is actually of any practical interest.