<blockquote>
<p>However, refer [sic] to this answer, <a href="https://stackoverflow.com/a/29146718/7721525">https://stackoverflow.com/a/29146718/7721525</a>, some implementation of introselect runs <code>2lg(n)</code> partition_pivot</p>
</blockquote>
<p>As mentioned in the comments there, that implementation is <em>named</em> introselect, but it does not actually implement the <a href="https://en.wikipedia.org/wiki/Introselect" rel="nofollow noreferrer">introselect algorithm</a>.</p>
<blockquote>
<p>How to achieve a worst time <code>O(n)</code> introselect?</p>
</blockquote>
<p>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 <a href="https://en.wikipedia.org/wiki/Median_of_medians" rel="nofollow noreferrer">median of medians</a> algorithm.</p>
<p>Note that there's also the recent <a href="https://arxiv.org/abs/1606.00484" rel="nofollow noreferrer">QuickSelectAdaptive algorithm</a> by A. Alexandrescu which goes into detail how to implement deterministic linear-time selection.</p>
How the worst time complexity of introselect become `O(n)`?
<p>The wikipedia <a href="https://en.wikipedia.org/wiki/Introselect" rel="nofollow noreferrer">introselect</a> says the worst time complexity is <code>O(n)</code>.</p>
<p>However, refer to this answer, <a href="https://stackoverflow.com/a/29146718/7721525">https://stackoverflow.com/a/29146718/7721525</a>, some implementation of introselect runs <code>2lg(n)</code> times of <code>partition_pivot</code>, which has a worst time complexity of <code>O(nlg(n))</code>. Whether you use medians_of_medians algorithm of heapsort, the time complexity is already <code>O(nlg(n))</code>.</p>
<p>How to achieve a worst time <code>O(n)</code> introselect?
If we use a constant <code>k</code> instead of <code>2lg(n)</code>. Can we say the time is <code>O(n)</code>? Can you give me some practical choices of k( must be a constant)?</p>