title: Average Runtime of Quickselect
body: <p>Wikipedia states that the average runtime of quickselect algorithm (<a href="http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm" rel="noreferrer">Link</a>) is O(n). However, I could not clearly understand how this is so.  Could anyone explain to me (via recurrence relation + master method usage) as to how the average runtime is O(n)? </p>