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]
views:
281answers:
7That's an overly simplistic argument. But it does happen to be correct in this case.
polygenelubricants
2010-05-05 14:50:26
well i don't see why complicate things :))it's not like he gave us a complete algorithm...
Mladen Prajdic
2010-05-05 15:32:49
This argument is faulty in general. You can have nested loops that's `O(N)`, and it can also be `O(2^N)`. It really depends on the algorithm itself, not just the structural nesting.
polygenelubricants
2010-05-05 14:53:35
Yah, you're right. Didn't think that one all the way through. Updated :)
Arve Systad
2010-05-05 15:45:42
Actually, given the initial assertion, it's best case is O(n^2). If the inner loop is doing something more than O(1), it is certainly not the worst case.
andand
2010-05-05 17:38:03
+4
A:
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).
Bill the Lizard
2010-05-05 14:46:53
+1 for hitting on the importance of the assumption of len(rotors)==len(widgets)
Platinum Azure
2010-05-08 17:58:46
+7
A:
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).
Matthew Flaschen
2010-05-05 14:47:17
+2
A:
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)
Kendall Hopkins
2010-05-05 14:48:00
+2
A:
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).
andand
2010-05-05 17:32:09
A:
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.
daveangel
2010-05-07 11:56:17