You are given a sequence of n elements to sort. The input sequence consists of 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 n/k subsequences.

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

This question was previously asked in

UGC NET Paper 3: Computer Science Nov 2017 Official Paper

- Ω (n)
- \(\Omega \left(\frac{n}{k}\right)\)
- Ω (n lg k)
- \(\Omega \left(\frac{n}{k}\; lg \frac{n}{k} \right)\)

Option 3 : Ω (n lg k)

Free

Official Paper 1: Held on 24 Sep 2020 Shift 1

12478

50 Questions
100 Marks
60 Mins

The correct answer is **option 3.**

**EXPLANATION**

There are \(n \over k\) subsequences and each can be ordered in k! ways. This makes a \( (k!)^{n \over k}\) outputs.

We can use the same reasoning:

\( (k!)^{n \over k} \le2 ^h\)

Taking the logarithm of both sides, we get:

h ≥ log(k!)^{n/k}

\(h \ge ({n \over k)}) log(k!)\)

\( \ge ({n \over k})({k \over 2})log({k \over 2}) \\ =\Omega (nlog k)\)

**Hence the correct answer is** *Ω (n log k).*

India’s **#1 Learning** Platform

Start Complete Exam Preparation

Daily Live MasterClasses

Practice Question Bank

Mock Tests & Quizzes

Trusted by 2,16,85,689+ Students

Testbook Edu Solutions Pvt. Ltd.

1st & 2nd Floor, Zion Building,

Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

[email protected]
Plot No. 273, Sector 10, Kharghar,

Navi Mumbai - 410210

Toll Free:1800 833 0800

Office Hours: 10 AM to 7 PM (all 7 days)