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)
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:
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).
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.
