Class Notes (838,093)
Canada (510,678)
CSC263H1 (54)
Lecture 10

Lecture 10.docx

3 Pages
Unlock Document

Computer Science
Toniann Pitassi

Analysis of RQS |S| = n, Worst Case: T(n) = (n-1) + T(n-1) T(n) is Ɵ(n^2) Fix some input S of n keys Run RQS of S Worst Case is Ɵ(n^2) key comparisons What is the expected cost? (Number of key comparisons) Over all possible random choices of pivot Rename the n keys of S as Z <1Z < 2 < Z < …jZ ) < Zij n Any 2 keys Z ind Z aje compared at most once 1iff Zi∧Zjarecompared Let Cij { 0otherwise Total cost of RQS is : ❑ C = ∑ Cij i< j ❑ ❑ Cij E(Cij) E(C) = E ( i< j ) = ∑i< j E(C )ij = 1* Prob[C =ij] + 0 * Prob[C = 0ij E(C ) = Prob [Z and Z are compared] ij i j 2 = j−i+1 Consider the set Z = ij , Zi, …i+1 j |Z ij= j - i + 1 Initially Zijs entirely contained in S. The RQS(S) algo keeps selecting pivots and uses them repeatedly split S into smaller and smaller subsets until it gets subsets of size ≤ 1 As long as the selected pivots are not in the set Z , theijZ remaiij entirely contained in one of the subset formed by pivots, and Z and i Z jemain uncompared. At some point, RQS(S) must select a pivot p∈Z ij. Focus on when this occurs:
More Less

Related notes for CSC263H1

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.