CODEWITHSUNDEEP
pythoniteratortime-complexity
Erik Pasztor
Erik Pasztor

Reputation: 11

time complexity of iteration in python

I have a question about iterating through a list in python. Let's say I have lists A = [1, 2, 3, 4] and B = []. What is the difference (if any) between using these two cycles? I'm intrested in the time complexity.

for i in range(len(A)):
    B.append(A[i])

for i in A:
    B.append(i)

Upvotes: 0

Views: 3000

Answers (3)

Joe Iddon
Joe Iddon

Reputation: 20424

The time-complexity is identical for both of those operations loops.

Think about it this way:

How many iterations will they have to do?

They'll both have to do len(A) number of loops. So therefore, they will take the same length of time.

Another way that this may be written is O(n). This is an example of Big-O-Notation and just means that the time-complexity is linear - i.e both of the operations will take the same amount of time longer if the list goes from being length 5 --> 10 as it would if the list went from being length 1000 --> 1005.

--

The other time-complexities can be seen clearly in the following grap which was stolen from this great explanation in another answer:

graph

Upvotes: 1

Ajax1234
Ajax1234

Reputation: 71451

Each loop is O(n), or linear time:

for i in range(len(A)):
    B.append(A[i])

for i in A:
    B.append(i)

Each append operation is O(1), and the indexing occurring at B.append(A[i]) is also O(1). Thus, the overall time complexity for this code block is:

T(N) = O(n) + O(n) = 2*O(n) => O(n)

since Big - O measures worst case.

Upvotes: 0

Silvan
Silvan

Reputation: 93

According to this question/answer, len(A) has a time-complexity of O(1), so it doesn't increase the complexity of the first loop that you mentioned. Both possibilities have to do n cycles, where n is the length of A. All in all, both possibilities have a time-complexity of O(n).

Upvotes: 0

Related Questions