CODEWITHSUNDEEP
pythontime-complexitybig-o
Dominique Randolph
Dominique Randolph

Reputation: 41

What is the algorithmic complexity of converting a collections.deque to python list?

I'm trying to determine the complexity of converting a collections.deque object into a python list object is O(n). I imagine it would have to take every element and convert it into the list, but I cannot seem to find the implementation code behind deque. So has Python built in something more efficient behind the hood that could allow for O(1) conversion to a list?

Edit: Based off the following I do not believe it could be any faster than O(n) "Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead."

If it cannot access a middle node in O(1) time it will not be able to convert without the same complexity.

Upvotes: 4

Views: 2813

Answers (2)

Arun Karunagath
Arun Karunagath

Reputation: 1588

Here is the implementation of deque

However, that is irrelevant for determining complexity to convert a deque to list in python.

If python is not reusing the data structure internally somehow, conversion into a list will require a walk through the deque and it will be O(n).

Upvotes: 0

Makoto
Makoto

Reputation: 106528

You have to access every node. O(1) time is impossible for that fact alone.

I would believe that a deque follows the same principles as conventional deques, in that it's constant time to access the first element. You have to do that for n elements, so the runtime to do so would be O(n).

Upvotes: 3

Related Questions