# Question

The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small relative to n, we can implement a different procedure that uses SELECT as a subroutine but makes fewer comparisons in the worst case.

a. Describe an algorithm that uses Ui (n) comparisons to find the ith smallest of n elements, where.

b. Show that, if i < n/2, then Ui (n) = n + O (T (2i) lg (n/i))..

c. Show that if i is a constant less than n/2, then Ui (n) = n + O (lg n)..

d. Show that if i = n/k for k ≥ 2, then Ui (n) = n + O (T (2n/k) lg k)..

a. Describe an algorithm that uses Ui (n) comparisons to find the ith smallest of n elements, where.

b. Show that, if i < n/2, then Ui (n) = n + O (T (2i) lg (n/i))..

c. Show that if i is a constant less than n/2, then Ui (n) = n + O (lg n)..

d. Show that if i = n/k for k ≥ 2, then Ui (n) = n + O (T (2n/k) lg k)..

## Answer to relevant Questions

A hash table of size m is used to store n items, with n ≤ m/2. Open addressing is used for collision resolution. a. Assuming uniform hashing, show that for i = 1, 2, ..., n, the probability that the ith insertion ...a. Suppose that m is a constant. Describe an O (n)-time algorithm that, given an integer n, outputs the (n, m)-Josephus permutation.b. Suppose that m is not a constant. Describe an O (n lg n)-time algorithm that, given ...In the depth-determination problem, we maintain a forest F = (Ti) of rooted trees under three operations:• MAKE-TREE (v) creates a tree whose only node is v.• FIND-DEPTH (v) returns the depth of node v within its ...Show that if (S, ℓ) is a matroid, then (S, ℓ′) is a matroid, where ℓ′ = {A′: S - A′ contains some maximal A ¬ℓ}. That is, the maximal independent sets of (S, ...When an adjacency-matrix representation is used, most graph algorithms require time Ω (V2), but there are some exceptions. Show that determining whether a directed graph G contains a universal sink-a vertex with ...Post your question

0