What is the big-O cost function of this algorithm?

How would you characterize the below in big-O notation?

rotors = [1,2,3,4,5 ...]
widgets = ['a', 'b', 'c', 'd', 'e' ...]

assert len(rotors) == len(widgets)

for r in rotors:
    for w in widgets:
        ...

    de开发者_Go百科l widgets[0]

It's O(n^2). You can see that the number of inner loop executions is:

n + (n - 1) + (n - 2) + ... + 1

because one widget is deleted every outer loop iteration. That is (n^2+n)/2, which is O(n^2).

since you're going through both loops it's O(n^2).

Because of the assertion:

assert len(rotors) == len(widgets)

the answers of O(n²) are correct, but in the general case where the lists aren't necessarily the same length, you'd call it O(m*n).

This algorithm will have a worst case performance of O(n^2).

It's O(n^2), but I think people are missing the delete part of this question.

The first loop you have n widgets.
The second loop you have n-1 widgets.
...
The n-1 loop you have 2 widgets.
The n loop you have 1 widgets.

You might think that you lower the Big-O but all the delete does is multiplying the coefficient by 1/2.

This is because n+(n-1)+...+2+1 = n(n+1)/2. As N goes to infinity it turns into n^2/2 which is just O(n^2)

At the risk of being both contrary and pedantic, you really haven't provided enough information to answer the question in general terms. Certainly the performance is no better than O(n^2), but since you give no details about what you're doing in the inner loop, it will in general be much worse. However, assuming that what's going on in the inner loop is O(1), then the overall performance is O(n^2).

Yeah that's why these big O problems are always hard to figure out. But if I had to guess I'd say O(n^2) since you are going through 2 for loops carrying out some operation each time.