Redirected
edited by
573 views
1 votes
1 votes

You are given a sequence of $n$ elements to sort. The input sequence consists of $\dfrac{n}{k}$ subsequences, each containing $k$ elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length $n$ is to sort the $k$ elements in each of the $\dfrac{n}{k}$ subsequences.

The lower bound on the number of comparisons needed to solve this variant of the sorting problem is

  1. $\Omega (n)$
  2. $\Omega \bigg( \dfrac{n}{k} \bigg)$
  3. $\Omega(n \lg k)$
  4. $\Omega \bigg( \dfrac{n}{k} \: \lg \: \dfrac{n}{k} \bigg)$
edited by

1 Answer

Answer:

Related questions

1 votes
1 votes
3 answers
1
Arjun asked Nov 5, 2017
837 views
Which of the following routing technique / techniques is/are used in distributed systems?Fixed RoutingVirtual RoutingDynamic Routing(a) only(a) and (b) only(c) onlyAll (a...
1 votes
1 votes
2 answers
3
Arjun asked Nov 5, 2017
908 views
The Sigmoid activation function $f(t)$ is defined as$\dfrac{1}{\text{exp} (t) + \text{exp} (-t)}$$t \text{ exp}(-t)$$\dfrac{1}{1+ \text{exp} (t)}$$\dfrac{1}{1+ \text{exp...