...
Question 6684 – Algorithms
November 26, 2023
Question 6864 – Algorithms
November 26, 2023
Question 6684 – Algorithms
November 26, 2023
Question 6864 – Algorithms
November 26, 2023

Question 6355 – Algorithms

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

Correct Answer: C

Question 343 Explanation: 
There are n/k subsequences and each can be ordered in k! ways. This makes a (k!)n/k outputs. We can use the same reasoning:
(k!)n/k ≤ 2h
Taking the logarithm of both sides, we get:
h ≥ lg(k!)n/k
= (n/k)lg(k!)
≥ (n/k)(k/2)lg(k/2)
= (1/2)*(nlogk)-(1/2)*n
= Ω(nlogk)
A
Ω(n)
B
Ω(n/k)
C
Ω(nlogk )
D
Ω(n/klogn/k)
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x