1
$\begingroup$

I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so I thought I'd post here.

def functionC(L):
    for i in range(len(L)):
        if L[i] == i:
            v = L.pop(i)
            L.insert(i, 2*v)
    return

I supplied the following answer:

The above function is O(n) because the for-loop grows with the size of L. The pop and insert functions are both constant time.

the word time is crossed out, but there is no other explanation as to why I received 6/10 for the question. What did I get wrong in this and why?

Here is an image of the question and my answer to prove the quiz has already been graded and handed back.

enter image description here

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You should ask this question to the person who graded you. $\endgroup$ – Yuval Filmus Mar 31 '20 at 17:53
  • $\begingroup$ @YuvalFilmus due to the COVID-10 virus, we don't have office hours anymore as we are all online now. I sent an email two days ago but still have not received a response so I came here as I am sure he is overwhelmed. $\endgroup$ – DMellon Mar 31 '20 at 17:54
  • $\begingroup$ BTW, "worst case O(n)" is a bit redundant. $\endgroup$ – Acccumulation Apr 1 '20 at 2:52
  • $\begingroup$ @Acccumulation "worst case O(n)" is not redundant. $\endgroup$ – Bernhard Barker Apr 1 '20 at 4:04
1
$\begingroup$

As pointed out by Yuval Filmus, you should ask that question to your professor.

I'll just point out some possible issues. I will also assume that $L$ is a python list.

  • $n$ is never defined, so it is unclear what $O(n)$ even means.

  • The wording "the for loop grows with the size of L" is a bit odd. A for loop does not grow. Its number of iterations is equal to the size (or better, length) of L.

  • From here, it seems that lists in python are implemented using arrays*. The $L.\mbox{pop}(i)$ operation requires $\Theta( 1 + \mbox{len}(L)-i )$ time** and, in your case, you can have $\Theta(\mbox{len}(L))$ iterations for which $\mbox{len}(L)-i = \Theta(\mbox{len}(L))$. The same holds for $L.\mbox{insert}(i, \cdot)$. The overall time complexity is then $O((\mbox{len}(L))^2)$. Consider, for example, the list $L = \langle 0, 1, \dots, \mbox{len}(L) \rangle$.

*These arrays are dynamically resized when elements are appended and not enough capacity is available. This only guarantees a constant amortized time per operation, so even a single operation on a list $L$ that you got as a parameter could cost up to $O(\mbox{len}(L))$ worst-case time. This is not a concern in your code since the initial capacity of $L$ is never exceeded.

**Some sources report that $L\mbox{.pop}(i)$ requires $O(i)$ time. The above argument still holds in this case.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ O(1+n^2) is the same thing as O(n^2). $\endgroup$ – Acccumulation Apr 1 '20 at 2:51
  • 1
    $\begingroup$ Any sources that claim L.pop(i) takes O(i) time are wrong. pop needs to shift all elements that came after the popped element, not the elements that came before it. $\endgroup$ – user2357112 supports Monica Apr 1 '20 at 3:08
  • $\begingroup$ Also, the resize strategy only guarantees constant amortized resize costs per operation - other costs of operations are not affected. $\endgroup$ – user2357112 supports Monica Apr 1 '20 at 3:10
  • $\begingroup$ "n is never defined" - n is conventionally the size of the input. While that, and the phrasing problem (the second point), could still contribute to getting marked down, the fact that the complexity given in the answer is just wrong (what you mentioned in the third point) is probably the primary contributor here. $\endgroup$ – Bernhard Barker Apr 1 '20 at 4:01
  • 1
    $\begingroup$ While the resulting complexity given in this answer is right, you seem to just be silently dropping the i from the analysis, which you can't really do, as it may change the complexity. Normally you'd need to sum up the running time of each iteration of the loop and then using some series formula to determine the result, but in this case the time of the two operations actually add up to len(L), which makes it simpler. $\endgroup$ – Bernhard Barker Apr 1 '20 at 4:20
2
$\begingroup$

You need to be aware that the complexity of insert and pop can be $O(n)$ in python ($n = \text{length($L$)}$). Hence, the time complexity can be $O(n^2)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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