According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof that if we do a formal analysis, we will get the following formula:

$$C_N = 2 N + 2 k ln (N / k) + 2 (N – k) ln (N / (N – k))$$

*$C_n$ is the number of compares if the array has N items.

Does anyone know how this formula is derived?


closed as unclear what you're asking by D.W., Luke Mathieson, vonbrand, Nicholas Mancuso, Thomas Klimpel Aug 5 '15 at 22:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ How do you get o(n) rather than O(n)? $\;$ $\endgroup$ – user12859 Jul 17 '15 at 2:54
  • 1
    $\begingroup$ "we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array." -- No, we don't. We show that the expected runtime it in $O(n)$ by showing that (in the random permutation model) we get rid of half the values in expectation. Are you familiar with the principles of average-case analysis? $\endgroup$ – Raphael Jul 17 '15 at 7:12
  • $\begingroup$ 1. Please provide more context. What's $k$? What's $C_N$? Is $C_N$ the expected number of comparisons, the worst-case number of comparisons, or something else? 2. What research have you done? Have you done some searching to look for lecture notes on QuickSelect? Have you looked at standard algorithms textbooks? Many algorithms textbooks, and many online resources, give a detailed explanation of the analysis of running time of QuickSelect. $\endgroup$ – D.W. Jul 18 '15 at 1:24
  • $\begingroup$ 3. In fact, the Wikipedia article on QuickSelect links to an analysis of QuickSelect's running time, which happens to give a similar (but not identical) formula and to explain where each term came from. Does that analysis help with your question? We expect you to do a significant amount of research before asking, and to show us in the question what you've done. [Generally, if the answer can be found by going to the obvious place on Wikipedia, you need to do more research before asking.] $\endgroup$ – D.W. Jul 18 '15 at 1:27
  • $\begingroup$ k is the index of the pivot. CLRS and algorithms by kevin wayne both do not have an analysis. Thats why i am asking. And i don't quite understand the article you linked. I ask here because I am looking for an easy to understand analysis, or intuition, even if it does not list the exact analysis. @D.W. $\endgroup$ – user10024395 Jul 19 '15 at 14:46