QuoteOriginally posted by: smiesQuicksort is O(n log n), but for median selection (or, for that matter, any element selection), once you've partitioned the data you only need to look at one half of it each time, so you average n + n/2 + n/4 + ... operations, which is O(n).That's still not O(n) in worst case, is it? There's a way to deterministically get worst case O(n) -- First, break the n elements into (n/5) chunks of 5 each. Find the median in each, find the median of these n/5 medians.Use that as your pivot -- this is guaranteed to have at least 3:7 or better partitioning of the list. (Why? Hint: medians)Process the partition you are interested in, it is at most as big as (7n/10)Recurrence relation for the complexity is T(n) = T(n/5) + T(7n/10) + O(1)Note that the problem size has decreased by a factor of 1/10, giving T(n) = O(n).

QuoteOriginally posted by: smiessee how much of Joshi's books I can get through (I've already started on the first one). Are there any particular parts I should focus on, or just work through it in order? And I presume it'd be beneficial to try and code some of the models?.start at the beginning and work your way through. Better to know the first half well than all poorly. Do the computer projects at the back of the book.