I am wondering about the time complexity of the get operation of deque in Python.
I know that it is implemented as a doubly link in Python. Does that mean that its time complexity is O(n)?
deque
are implemented a little smarter than just doubly-linked lists. They're a doubly-linked list of blocks of Python objects, where the left and right sides may be incomplete blocks.
The Big-O cost of accessing in the middle is still O(n)
, but it has a constant divisor (implementation dependent, CPython 3.5 allocates blocks that can store 64 objects). So if your deque
has 1000 members, accessing in the middle still involves only around 7-8 "linked list-style" traversals, not 500-some. If the deque
is smallish (65 to 128 elements, depending on how the empty slots align with the head and tail blocks), then lookup of any element is equal cost.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With