datastructures-js / queue Goto Github PK

Hello, I wonder why dequeuing all elements runs in $O(n \log n)$? The following operation will only run $\log n$ times:

// only remove dequeued elements when reaching half size
// to decrease latency of shifting elements.
this._elements = this._elements.slice(this._offset);

And since Array.slice() runs in $O(n)$, the complexity should be: $$\frac{n}{2} + \frac{n}{4} + \cdots + 1 < \frac{n}{2} + \frac{n}{4} + \cdots = \frac{n}{2} \cdot \sum_{i=0}^{\infty} \frac{1}{2^i} = \frac{n}{2} \cdot 2 = n = O(n)$$

So the overall complexity of dequeuing all elements should be $O(n + n) = O(n)$, and hence the amortized complexity of dequeue() is $O(1)$. Please correct me if I am wrong :)

deque which allows push_front & pop_back, is a very useful data structure
when it comes to inserting/ deleting either ends

https://en.cppreference.com/w/cpp/container/deque

we can create a new data structure with name deque
or
allow one more param in constructor of queue, that enables it to work like deque and has similar operation to pop_back

what are your views on this? thanks