CSC263H1 Lecture Notes - Lecture 10: Zij
22 Apr 2014
School
Department
Course
Professor
Document Summary
|s| = n, worst case: t(n) = (n-1) + t(n-1) What is the expected cost? (number of key comparisons) Rename the n keys of s as z1 < z2 < < zj < (zij) < zn. Any 2 keys zi and zj are compared at most once. = 1* prob[cij = 1] + 0 * prob[cij = 0] E(cij) = prob [zi and zj are compared] Consider the set zij = {zi , zi+1, zj} Initially zij is entirely contained in s. the rqs(s) algo keeps selecting uses them repeatedly split s into smaller and smaller pivots and subsets until it gets subsets of size 1. As long as the selected pivots are not in the set zij, then zij remains contained in one of the subset formed by pivots, and zi and uncompared. At some point, rqs(s) must select a entirely.
