CODEWITHSUNDEEP
algorithmbig-o
ʞɔıu
ʞɔıu

Reputation: 48426

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

    del widgets[0]

Upvotes: 3

Views: 528

Answers (7)

daveangel
daveangel

Reputation: 573

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.

Upvotes: 0

andand
andand

Reputation: 17497

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

Upvotes: 2

Arve Systad
Arve Systad

Reputation: 5479

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

Upvotes: 3

Kendall Hopkins
Kendall Hopkins

Reputation: 44104

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)

Upvotes: 2

Matthew Flaschen
Matthew Flaschen

Reputation: 284836

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

Upvotes: 7

Bill the Lizard
Bill the Lizard

Reputation: 405795

Because of the assertion:

assert len(rotors) == len(widgets)

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

Upvotes: 4

Mladen Prajdic
Mladen Prajdic

Reputation: 15677

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

Upvotes: 5

Related Questions