CODEWITHSUNDEEP
algorithmsortingdecision-treelower-bound
Jake Senior
Jake Senior

Reputation: 233

Decision tree of sorting groups into a list

Give a lower bound on the time to produce a single sorted list of n numbers that are in k groups. Such that the smallest n/k are first and so on.

So I have been stuck at this problem for a while and I'm really unsure how to go about it. I know how to make a decision tree, but i don't understand how I'm supposed to do it in the context of this problem. I don't necessarily understand the problem, yet it seems to be clear enough to be solved for people. Any point in the right direction or clarification would be extremely appreciated.

Upvotes: 1

Views: 165

Answers (2)

CiaPan
CiaPan

Reputation: 9570

I'm not sure what is a "lower bound" in the question.

If

(...) numbers that are in k groups. Such that the smallest n/k are first and so on.

means groups are already sorted (given in proper order), then

the time to produce a single sorted list

is minimum if the numbers inside groups are already sorted. Then the minimum time to produce a sorted list is k*(n/k-1) + k*(n/k) + (k-1) = O(n+k) for testing each of 'k' groups for being already sorted, converting each group into linked lists by appending each item in order and then concatenating groups into a single result list or array.

On the other hand, if we want the minimum time required to build the result despite the initial (lack of) order of input numbers in groups, then the answer is O(k*(n/k)*ln(n/k)) + n = O(n*ln(n/k)) for general algorithm sorting k groups n/k items each, then placing all n items in a resulting list or array.

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522007

Your question is difficult, because it assumes that the n numbers have been divided into k groups, with the groups themselves being ordered. I will assume here that the numbers within each group are not ordered. If the numbers were already sorted within each group, it would render the problem trivial.

The decision tree to solve your question could be built with k subtrees, one for each group, with each subtree connecting to the next subtree. The reason for this is that the groups themselves are already sorted, and we only need to sort each group. The lower bound running time would occur if we only had to traverse this tree along one path to find the correct leaf node (and sorted list). This means the lower bound is the height of the tree, which is:

O(k * lg n/k)

To break down this expression:

lg n/k is the height of each of the k subtrees

k * lg n/k is the height of the complete decision tree (there are k subtrees)

Please read this excellent PDF from the CS 401 class at the University of Illinois at Chicago which will completely explain your original problem and also show you a proof for how I arrived at the Big Omega expression I gave above.

Upvotes: 1

Related Questions