3 ms·
Where are you getting O(sqrt(n)) space from? The linked article says O(n) for compact dynamic arrays.
by mnarayan01 9y ago
Where are you getting O(sqrt(n)) space from? The linked article says O(n) for compact dynamic arrays.
- wuch 9y agoNote 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.