Give an algorithm that finds the median value

Assignment Help Database Management System

Reference no: EM132101948

Problem

You are interested in analyzing some hard- to-obtain data from two separate databases. Each database contains n numerical values, so there are 2n values total and you may assume that no two values are the same.

You'd like to determine the median of this set of 2n values, which we will define here to be the n-th smallest value.

However, the only way you can access these values is through queries to the databases.

In a single query, you can specify a value k to one of the two databases, and the chosen database will return the k-th smallest value that it contains. Since queries are expensive, you would like to compute the median using as few queries as possible.

Give an algorithm that finds the median value using at most O(log n) queries.

Reference no: EM132101948

Questions Cloud

How do the different stages of production : How do the different stages of production inform what we ultimately see on the screen?

Write a program that generates three random rational numbers : Write a program that generates three random rational numbers between -10 and 10. Label the numbers A, B, and C.

Why is freedom an essential question for ethics : Why is Freedom an essential question for ethics? review at least four arguments against the existence of freedom.

Why is freedom an essential question for ethics : Why is Freedom an essential question for ethics? In your answer, review at least four arguments against

Give an algorithm that finds the median value : You are interested in analyzing some hard- to-obtain data from two separate databases. Give an algorithm that finds the median value.

What nietzsche mean by the death of god : Have they continued? In our own time, does what passes for belief in God (at least for many people) refute or confirm Nietzsche's prediction. what Nietzsche mea

How does confucius understand virtue : How does Aristotle understand virtue? And how does Confucius understand virtue?

What is the theoretical view of a human being : What is the theoretical view of a human being? With the topic of human rights and human dignity being incorporated?

Identify a major nonverbal behavior in your culture : Identify a major nonverbal behavior in your culture. Consider how someone outside of the culture might react to this nonverbal behavior.

User Account

All Pages