CODEWITHSUNDEEP
pythontime-complexity
Dean Wong
Dean Wong

Reputation: 283

What is the time complexity of zip() in Python?

How can I calculate the time complexity of zip()?

testList = [[1,2,3]for _ in range(5)]
zip(*testList)

Upvotes: 23

Views: 17703

Answers (1)

Tamas Hegedus
Tamas Hegedus

Reputation: 29946

Assume you zip N iterables.

In python 3.x, the zip function itself runs in O(1) time, as it just allocates a special iterable (called the zip object), and assigns the parameter array to an internal field. The function invocation itself (before control reaches in zip) is O(N), as the interpreter must convert the parameters to an array. Every subsequent next call on the iterator also runs in O(N). Exhausting the zip object is therefore O(N*M) assuming M is the average (or minimum) length of the iterables, excluding the time the iterables themselves take to generate items (as it is independent of zip).

In python 2.x, the zip function returns a list. That list must be constructed during the call, that is equvivalent to exhausting the iterator in the previous example, so O(N*M), not counting the time spent in the zipped iterables.

Upvotes: 29

Related Questions