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

Lecture 10.docx

3 Pages
121 Views
Unlock Document

Department
Computer Science
Course
CSC263H1
Professor
Toniann Pitassi
Semester
Winter

Description
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


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit