CSCC73H3 Lecture Notes - Multiplication Algorithm, Mathematical Induction, Primitive Root Modulo N

115 views4 pages
19 Oct 2011
School
Course

Document Summary

Let d1 and d2 be the two databases, each containing n elements. Recall that the median of 2n (distinct) elements has exactly n elements larger than it, and exactly n 1 elements smaller than it. Let query(t, di) return the element ranked t-th in the database di. By applying query(m, d1) and query(m, d2) we can nd the values of the m-th elements, a1 and a2, of d1 and d2, respectively. Now we claim that by comparing a1 to a2, we can eliminate as potential candidates for the overall median half of the elements of each database. To see why, suppose a1 < a2 (the case a2 < a1 is symmetric). Similarly, none of the last m elements in. Thus, with two queries we can eliminate from consideration half the elements of each database. Continuing in the same way, after log2 n steps we will have eliminated from consideration all but one element in each database.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions