1
$\begingroup$

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)
            answer = answer - L[i]   # O(1)

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)?

$\endgroup$

closed as off-topic by David Richerby, xskxzr, Discrete lizard Apr 20 at 14:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, Discrete lizard
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Apr 18 at 20:19
  • $\begingroup$ Note that we discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you're not sure about your answer, that often indicates there is some concept you're not clear on. $\endgroup$ – D.W. Apr 18 at 20:20
  • 1
    $\begingroup$ The answer to your question comes down to exactly how Python implements range and so on, which is off-topic, here. $\endgroup$ – David Richerby Apr 18 at 21:20
  • $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – xskxzr Apr 19 at 10:20
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ yes I did mean O(n^2) as my final conclusion, (just changed it in the question) thanks a lot for your response :) $\endgroup$ – Emma Pascoe Apr 18 at 21:31
  • $\begingroup$ Of course! I am also a new contributor here, so if my answer was satisfactory please accept it! $\endgroup$ – Bryce Kille Apr 18 at 21:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.