4 ms·

If you randomize the values, the expected running time of your algorithm will be O(nlogn). Worst case is still O(n^2). Additionally, the adversarial argument pr

If you randomize the values, the expected running time of your algorithm will be O(nlogn). Worst case is still O(n^2). Additionally, the adversarial argument presented is voided because it relies on deterministically placed elements, which allows the adversary to actually choose them on the fly. In general, a randomized algorithm is better than its deterministic counterpart. Citation: I'm a 15-451 (Algorithm Design and Analysis) TA at Carnegie Mellon and I just gave this lecture in recitation.

gjm11 16y ago
> it relies on deterministically placed elements Did you read the paper? If you provide McIlroy's adversarial comparison function to a (no matter how genuinely) randomized quicksort algorithm, then typically it will provoke quadratic-time behaviour, and the final state of the array will be such that passing it into the quicksort function would have produced that same quadratic-time behaviour, given the same random choices. (See the paragraph beginning "The adversarial method works for almost any polymorphic program recognizable as quicksort".) What the adversary can't do, of course, is to produce an array that on a subsequent run, with different random choices, will again provoke bad behaviour. The average case of quicksort is O(n log n), and nothing McIlroy's adversary can do will change that.
- jchonphoenix 16y ago
  No, actually it does rely on deterministically placed elements. And its analyzing unix qsort which is a deterministic algorithm. Unless I'm misunderstanding the paper (which I could be). The argument relies on the fact that the adversary can choose the elements on the fly. This requires the input be deterministic so that the adversary knows what elements are where. If you randomize the input, the adversary will have no knowledge of the input and thus is not able to choose which elements go in which index. This would be randomly generated. For more information on the adversarial method see: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ Recitation 09/08 explains this problem in depth.
  - util 16y ago
    I get permission denied when trying to view that page. Would be interested in seeing it.
    - jchonphoenix 16y ago
      Fixed :)
- jchonphoenix 16y ago
  "An adversary can make such a quicksort go quadratic by arranging for the pivot to compare low against almost all items not seen during pivot selection, so the partition will be lopsided. Those items may be regarded as a “gas” of values whose relationship to each other is unknown. The exact values don’t matter as long as they are not compared against each other. Quadratic behavior is guaranteed since n − O(1) gas values must survive pivot selection among n items. Almost all partition high." This paragraph from the paper is a false statement when applied to randomized quicksort. The adversary cannot "arrange for the pivot to compare low against all items not seen during pivot selection," if quicksort was randomized namely because the adversary has no information about the other elements. In deterministic quicksort he does. Thus, this is where his argument breaks down in relation to randomized quicksort. I think he focused on deterministic and just tacked on the statement about randomized without thinking about it. Its a very subtle error to make when using the adversarial method against a randomized algorithm and because his analysis deals with deterministic quicksort I doubt he put much thought into the randomized case.
  - gjm11 16y ago
    > This paragraph from the paper is a false statement when applied to randomized quicksort. Looks OK to me subject to the criteria McIlroy gives for the success of his method. (You did read the whole paper, not just that paragraph, right?) His adversary effectively incorporates a heuristic for telling when the pivot is being selected! See http://pastebin.com/5B5qffJt http://pastebin.com/5B5qffJt for a simple demonstration of McIlroy's adversary in action against a randomized quicksort implementation. If you run the code there, you'll find that the "good" case (without the McIlroy adversary) typically takes about 1.5 n log n comparisons, and the "evil" case (with the McIlroy adversary) typically takes about 0.5 n^2 comparisons.
    - jchonphoenix 16y ago
      The issue isn't with the code. What I'm saying is that the code you produced is effectively a counterargument to deterministic quicksort and doesn't apply in the random case. What McIlroy is doing is selecting an element on the fly during the algorithm. If quicksort was randomized, he would not be able to do so. Thus his argument breaks down there. If you are constructing a "worst case" for randomized quicksort, the answer is still obviously O(n^2), but the purpose of randomized quicksort is that it is O(nlogn) EXPECTED running time. Thus, by constructing a worst case input, you really haven't broken randomized quicksort at all. In fact, you're doing exactly what its intended to do: perform badly sometimes, perform well other times, and in the expected case, perform O(nlogn). I read the entire paper, and I'm, of course, no expert, but I've ran my argument past a professor in algorithms (who is a Turing award winner), and he also believes that McIlroy's argument does not work for the randomized case. His heuristic cannot be legitimately applied in the randomized case because the adversary simply is not allowed to choose elements in the randomized case. That, of course, is the purpose of randomization. Thus, it doesn't matter what his code or heuristic shows. His argument has a logical fallacy and thus is illegitimate (only when applied to the randomized case of course).

gjm11 16y ago

> it relies on deterministically placed elements Did you read the paper? If you provide McIlroy's adversarial comparison function to a (no matter how genuinely) randomized quicksort algorithm, then typically it will provoke quadratic-time behaviour, and the final state of the array will be such that passing it into the quicksort function would have produced that same quadratic-time behaviour, given the same random choices. (See the paragraph beginning "The adversarial method works for almost any polymorphic program recognizable as quicksort".) What the adversary can't do, of course, is to produce an array that on a subsequent run, with different random choices, will again provoke bad behaviour. The average case of quicksort is O(n log n), and nothing McIlroy's adversary can do will change that.

jchonphoenix 16y ago
No, actually it does rely on deterministically placed elements. And its analyzing unix qsort which is a deterministic algorithm. Unless I'm misunderstanding the paper (which I could be). The argument relies on the fact that the adversary can choose the elements on the fly. This requires the input be deterministic so that the adversary knows what elements are where. If you randomize the input, the adversary will have no knowledge of the input and thus is not able to choose which elements go in which index. This would be randomly generated. For more information on the adversarial method see: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/ Recitation 09/08 explains this problem in depth.
- util 16y ago
  I get permission denied when trying to view that page. Would be interested in seeing it.
  - jchonphoenix 16y ago
    Fixed :)
jchonphoenix 16y ago
"An adversary can make such a quicksort go quadratic by arranging for the pivot to compare low against almost all items not seen during pivot selection, so the partition will be lopsided. Those items may be regarded as a “gas” of values whose relationship to each other is unknown. The exact values don’t matter as long as they are not compared against each other. Quadratic behavior is guaranteed since n − O(1) gas values must survive pivot selection among n items. Almost all partition high." This paragraph from the paper is a false statement when applied to randomized quicksort. The adversary cannot "arrange for the pivot to compare low against all items not seen during pivot selection," if quicksort was randomized namely because the adversary has no information about the other elements. In deterministic quicksort he does. Thus, this is where his argument breaks down in relation to randomized quicksort. I think he focused on deterministic and just tacked on the statement about randomized without thinking about it. Its a very subtle error to make when using the adversarial method against a randomized algorithm and because his analysis deals with deterministic quicksort I doubt he put much thought into the randomized case.
- gjm11 16y ago
  > This paragraph from the paper is a false statement when applied to randomized quicksort. Looks OK to me subject to the criteria McIlroy gives for the success of his method. (You did read the whole paper, not just that paragraph, right?) His adversary effectively incorporates a heuristic for telling when the pivot is being selected! See http://pastebin.com/5B5qffJt http://pastebin.com/5B5qffJt for a simple demonstration of McIlroy's adversary in action against a randomized quicksort implementation. If you run the code there, you'll find that the "good" case (without the McIlroy adversary) typically takes about 1.5 n log n comparisons, and the "evil" case (with the McIlroy adversary) typically takes about 0.5 n^2 comparisons.
  - jchonphoenix 16y ago
    The issue isn't with the code. What I'm saying is that the code you produced is effectively a counterargument to deterministic quicksort and doesn't apply in the random case. What McIlroy is doing is selecting an element on the fly during the algorithm. If quicksort was randomized, he would not be able to do so. Thus his argument breaks down there. If you are constructing a "worst case" for randomized quicksort, the answer is still obviously O(n^2), but the purpose of randomized quicksort is that it is O(nlogn) EXPECTED running time. Thus, by constructing a worst case input, you really haven't broken randomized quicksort at all. In fact, you're doing exactly what its intended to do: perform badly sometimes, perform well other times, and in the expected case, perform O(nlogn). I read the entire paper, and I'm, of course, no expert, but I've ran my argument past a professor in algorithms (who is a Turing award winner), and he also believes that McIlroy's argument does not work for the randomized case. His heuristic cannot be legitimately applied in the randomized case because the adversary simply is not allowed to choose elements in the randomized case. That, of course, is the purpose of randomization. Thus, it doesn't matter what his code or heuristic shows. His argument has a logical fallacy and thus is illegitimate (only when applied to the randomized case of course).