Big Oh Time Complexity Involving 'for i in range(n)' [closed]

Given the code below and the comment analysis:

n = len(L)  # O(1)
for i in range(n):  # O(n) - I read online that range(n) will take constant time
but the 'for i in range(n)' part would make this O(n)?
if L[i] > 0 :  # O(1)
for j in range(n):  # O(n)
answer = answer + L[i]  # O(1) - since indexing takes constant time
else :  # O(1)
for j in range(n):  # O(n)


My Overall Analysis:

• $$O(1)$$ for the first variable assignment
• first if statement takes overall $$O(n)$$
• else statement also takes overall $$O(n)$$ => Overall if/else statements take $$O(n)$$ as well
• for loop iterates n times => $$O(n * n)$$ => $$O(n^2)$$

=> Overall time complexity $$O(n^2)$$

Thanks in advance for the suggestions!

EDIT: I am wondering if the

for i in range(n)


portion of the code takes O(n) or O(1)? I read that range(n) would take O(1) but since its a for loop it would take O(n)?

• I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question about your exercise. Can you edit your question accordingly?
– D.W.
Apr 18 '19 at 20:19
– D.W.
Apr 18 '19 at 20:20
• The answer to your question comes down to exactly how Python implements range and so on, which is off-topic, here. Apr 18 '19 at 21:20
• Possible duplicate of Is there a system behind the magic of algorithm analysis? Apr 19 '19 at 10:20

So you have the right logic, if you have a loop of $$O(n)$$ iterations, the complexity of the entire loop will be $$O(n*\text{complexity of loop operations})$$. In this case, you again are correct that your loop's complexity is $$O(n)$$ for each iteration.
Your last bullet point shows that you understand this as well, as the total loop complexity is then $$O(n^2)$$. However, this trivially results in an overall time complexity of $$O(n^2)$$, not $$O(n)$$ as you concluded.
I imagine what you were really asking about is the complexity of range(n). While it is true that the initial call to range is $$O(1)$$, that is because it produces a generator which takes $$O(1)$$ to return the next successive value i.e. it doesn't produce the entire range right away, but instead on demand. However, keep in mind that the generator will be advanced $$O(n)$$ times (once for every iteration of the loop).