Class Notes (811,692)
CSC263H1 (54)
Lecture 14

# Lecture 14-15.docx

2 Pages
89 Views

Department
Computer Science
Course
CSC263H1
Professor
Toniann Pitassi
Semester
Winter

Description
Dynamic Tables T a) Expansion: If ⍺(t) = 1 and INSERT occurs then size(new_T) = 2size(T) b) Contraction: If ⍺(T) = 1/4 and DELETE occurs then size(new_T) = 1/2 size(T) Goals: ⍺(T) ≥ some constant (always) Amortized cost of insert/delete should be ≤ some constant Each INSERT is charged \$3: - 1 for actual cost - 2 credit IF a occurs, there were at least n/2 inserts. These generated a total of n/2 *\$2 = \$n. This covers the cost of the expansion Each DELETE is charged \$2 - \$1 covers the actual cost of delete
More Less

Related notes for CSC263H1
Me

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.