At the algorithm SELECT, there is the following step:

If $i=k$, then return $x$. Otherwise, use SELECT recursively to find the $i$th
smallest element on the low side if $i<k$, or the $i-k$ th smallest element on
the high side if $i>k$.

How could we find the cost of this step?

  • 1
    $\begingroup$ did you have a look at 'Analysis of Algorithms' on Coursera? $\endgroup$ – Alex Mar 6 '15 at 22:11
  • $\begingroup$ No, I have the book Introduction to algorithms by Cormen.. @Alex $\endgroup$ – evinda Mar 6 '15 at 22:18
  • $\begingroup$ In the Coursera courses (2 different actually) both algorithms are explained quite well $\endgroup$ – Alex Mar 6 '15 at 22:26
  • $\begingroup$ @Alex Can I find these courses online? $\endgroup$ – evinda Mar 6 '15 at 22:30
  • $\begingroup$ class.coursera.org/aofa-004/lecture $\endgroup$ – Alex Mar 6 '15 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.