[grillorafael]

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]

> 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]

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]

yes but they will share the same complexity

[Someone]

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]

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]

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]

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]

This is wrong.

See https://en.m.wikipedia.org/wiki/Quicksort, section "Selection-based pivoting".