I have an unsorted list of n elements. Assume I can find the kth smallest of the

Question

I have an unsorted list of n elements. Assume I can find the kth smallest of them using a SELECT procedure, which takes exactly 5n milliseconds; I can also sort the elements in 3nlog n milliseconds. If the list is sorted, it is stored in an array that I can access any location in
a single millisecond. A selection query is one that asks "what is the ith smallest element of this list?" If I will be making j such queries on the same list, for what values of j does it make more sense to sort the list first and access the array j times, rather than perform j SELECT operations? You should be giving me a formula in terms of n.

Explanation / Answer

Given that there is an unsorted list of n elements.

Case I:

To find the kth smallest element using a SELECT procedure, it takes 5n milliseconds.

So, for 1 query it takes 5*n milliseconds.

For j such queries, the amount of time required is 5*n*j milliseconds. Let this be equation 1.

Case II:

The array can be sorted in 3nlogn milliseconds and each query after sorting takes 1 millisecond.

So, for sorting time required= 3*n*log(n)

For 1 query, it takes 1 millisecond after sorting.

For j such queries, it will j milliseconds after sorting.

Hence, total time required for j queries = sorting time + time required for j queries

= 3*n* log(n) + j

Let this be equation 2.

To find out the value of j where sorting the list first and then accessing the array makes more sense than simply performing j select operations, we need to equate the above two equations:

3*n* log(n) + j = 5*n*j

=> j*(5*n – 1) = 3*n* log(n)

=> j = (3*n* log(n)) / (5*n – 1)

Thus, the value of j should be (3*n* log(n)) / (5*n – 1).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.