25 ms·

Yes. If the java have a different complexity it is a different algorithm. To the writers defense, they have to algorithm in pseudo code in the article

brazzy 8y ago
> If the java have a different complexity it is a different algorithm. It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.
- ehsankia 8y ago
  Right, like how Quicksort can be pretty different depending on how you choose the pivot. It's still Quicksort, but there's different variants.
  - grillorafael 8y ago
    yes but they will share the same complexity
    - Someone 8y ago
      You can make the average-case perform in O(n^2) by always pivoting on the smallest number in the array. Nobody would do _that_, but it shows that pivot choice can affect complexity. Ergo, computer scientists researching the algorithm mathematically must consider the effect of choice of pivot.
    - FreeFull 8y ago
      Depending on how you choose the pivot, the worst-case of complexity of Quicksort can be O(n^2) or O(n log n)
      - klmr 8y ago
        No, worst-case complexity of real quicksort is always O(n^2), regardless of pivot choice strategy (even with stochastic pivot choice, although you’d have to get very unlucky to hit that worst case). You can make the average case better or worse though. The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.
        PL_kolek 8y ago
        Isn't there a linear time median selection algorithm, which allows you to always select a pivot in the middle of the sorted part and create two equal halves? This produces a worst-case O(n log n) quick sort, which is no longer quick due to the big constant hidden in O notation.
        nh2 8y ago
        Correct, Quicksort with Quickselect for pivot choice.
        deathanatos 8y ago
        "quickselect" is a selection algorithm that uses a partial quicksort in order to do a select. You're essentially saying to write quicksort using quicksort. Quickselect requires a pivot choosing strategy; the problem is not only the same as quicksort's, it is the problem from quicksort. According to Wikipedia, in the worst case, it is O(n²).[1] But that's not strictly correct, IMO. Regardless, it doesn't answer the OP's question of "is there a selection algorithm that operates in worst case O(n)" [1]: https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect [2]: https://news.ycombinator.com/item?id=17888755 https://news.ycombinator.com/item?id=17888755 and the parent comment; specifically, the median-of-medians algorithm is a worst-case O(n) selection algorithm.
        nh2 8y ago
        This is wrong. See https://en.m.wikipedia.org/wiki/Quicksort https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".

brazzy 8y ago

> If the java have a different complexity it is a different algorithm. It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.

ehsankia 8y ago
Right, like how Quicksort can be pretty different depending on how you choose the pivot. It's still Quicksort, but there's different variants.
- grillorafael 8y ago
  yes but they will share the same complexity
  - Someone 8y ago
    You can make the average-case perform in O(n^2) by always pivoting on the smallest number in the array. Nobody would do _that_, but it shows that pivot choice can affect complexity. Ergo, computer scientists researching the algorithm mathematically must consider the effect of choice of pivot.
  - FreeFull 8y ago
    Depending on how you choose the pivot, the worst-case of complexity of Quicksort can be O(n^2) or O(n log n)
    - klmr 8y ago
      No, worst-case complexity of real quicksort is always O(n^2), regardless of pivot choice strategy (even with stochastic pivot choice, although you’d have to get very unlucky to hit that worst case). You can make the average case better or worse though. The only way of making quicksort’s worst-case runtime O(n log n) is by limiting recursion depth, as done e.g. in introsort. But that’s no longer quicksort.
      - PL_kolek 8y ago
        Isn't there a linear time median selection algorithm, which allows you to always select a pivot in the middle of the sorted part and create two equal halves? This produces a worst-case O(n log n) quick sort, which is no longer quick due to the big constant hidden in O notation.
        nh2 8y ago
        Correct, Quicksort with Quickselect for pivot choice.
        deathanatos 8y ago
        "quickselect" is a selection algorithm that uses a partial quicksort in order to do a select. You're essentially saying to write quicksort using quicksort. Quickselect requires a pivot choosing strategy; the problem is not only the same as quicksort's, it is the problem from quicksort. According to Wikipedia, in the worst case, it is O(n²).[1] But that's not strictly correct, IMO. Regardless, it doesn't answer the OP's question of "is there a selection algorithm that operates in worst case O(n)" [1]: https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect [2]: https://news.ycombinator.com/item?id=17888755 https://news.ycombinator.com/item?id=17888755 and the parent comment; specifically, the median-of-medians algorithm is a worst-case O(n) selection algorithm.
      - nh2 8y ago
        This is wrong. See https://en.m.wikipedia.org/wiki/Quicksort https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".