CODEWITHSUNDEEP
pythonalgorithmbig-o
DougM
DougM

Reputation: 940

Can you help me find the worst-case big-O time complexity for this code?

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 due to COVID-19 so I thought I'd post here as I have yet to hear a response.

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

Upvotes: 1

Views: 154

Answers (2)

sowrov
sowrov

Reputation: 1050

If you look into this python wiki time-complexity document, you will see the complexity of Pop intermediate and insert are listed as O(n) which in turns makes the above code O(n^2)

Upvotes: 0

aeternalis1
aeternalis1

Reputation: 675

Popping from and inserting into the middle of an array is O(N) time in terms of the length of the array. Thus overall time complexity is O(N^2). You only get O(1) pop and insert when working with the end of the array, since the rest of the elements don't have to be shifted, but it's O(N) elsewhere.

Upvotes: 2

Related Questions