1

The wikipedia introselect says the worst time complexity is O(n).

However, refer to this answer, https://stackoverflow.com/a/29146718/7721525, some implementation of introselect runs 2lg(n) times of partition_pivot, which has a worst time complexity of O(nlg(n)). Whether you use medians_of_medians algorithm of heapsort, the time complexity is already O(nlg(n)).

How to achieve a worst time O(n) introselect? If we use a constant k instead of 2lg(n). Can we say the time is O(n)? Can you give me some practical choices of k( must be a constant)?

Voyager
  • 727
  • 8
  • 26
  • Your question is unclear. Specifically, there are some claims that I am not sure where they are arriving from. Mostly: `partition_pivot which has a worst time complexity of nlg(n)`. Moreover, the fact that **an** implementation is suboptimal does not mean the algorithm itself cannot be implemented better. – amit Jun 30 '21 at 14:55
  • @amit thanks, I means `2lg(n)` times of `partition_pivot` – Voyager Jun 30 '21 at 17:10

1 Answers1

1

However, refer [sic] to this answer, https://stackoverflow.com/a/29146718/7721525, some implementation of introselect runs 2lg(n) partition_pivot

As mentioned in the comments there, that implementation is named introselect, but it does not actually implement the introselect algorithm.

How to achieve a worst time O(n) introselect?

You perform quickselect using either a constant number of partitions, or require that the partition is highly imbalanced at most a constant amount of times, and if not done within these restrictions you switch to the median of medians algorithm.

Note that there's also the recent QuickSelectAdaptive algorithm by A. Alexandrescu which goes into detail how to implement deterministic linear-time selection.

orlp
  • 112,504
  • 36
  • 218
  • 315
  • What if `n` is very large? Is the constant `k` unrelated to `n`? And `k` is closed to `log(n)`, if we still claim it `O(n)` algorithms, how about radix sort? When talk about radix sort time complexity, it's `O(n*w)` where `w` is length of key. – Voyager Jun 30 '21 at 17:12
  • 1
    @Voyager Read it yourself in the original paper, page 9. *Introspective Sorting and Selection Algorithms* by David R. Musser. Radix sort is something completely different. – orlp Jun 30 '21 at 17:35