# What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

223 views

## Problem :

I have below doubts regarding sorting:

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?

Does it change depending on the algorithm?

Can anybody clear my doubts?

## Solution :

The Best case happens when we just check the every element and see that the data is already sorted.

This results in n-1 comparisons and so the leaf will have a depth of n-1.

Practically speaking this happens for insertion sort.

Does it change depending on the algorithm?

It will change according to Algorithm. Here the best case of an algorithm is the good indicator - the shortest depth for one with O(n log n) the best case would be longer than the shortest depth for the one with O(n) best case.

To see this please consider the graph of n nodes, each node is representing A[i]. Draw the directed edge from i to j and if we compare A[i] with A[j] on the path from root to . Note that for k < n−1, this graph on {1, . . . , n} will not be connected. So we have two components C1 and C2 and so we know nothing about the relative order of the array elements indexed by the C1 against elements indexed by the C2. So there cannot be a single permutation π that sorts all the inputs passing these k tests - so π() is wrong for some arrays which lead to leaf

The leaf of the decision tree always has depth n-1.

# What is the smallest possible depth of a leaf in a decision tree for a sorting algorithm?

The shortest possible depth is n-1. To see this, observe that if we have a root leaf path with k comparisons, we cannot sure that the permutation at the leaf l is the correct one.

## Proof:

To see this consider a graph of n nodes, each node representing A[i]. Draw an edge from I to j if we compare A[i] with A[j] on the path from the root to l.

Hence we have two components C1 and C2, and we know nothing about the relative order of array element indexed C1 and C2 against elements indexed by C2. Therefore there cannot be a single permutation that sorts all inputs passing these k tests.

## Does it change depends on the algorithms?

It will change according to algorithms. Here is the best case of an algorithm and treated as a good indicator. The shortest depth for one with complexity O (n logn) with the best case would be larger than the shortest depth for the ones with the complexity O(n) of the best case.

### Note:

The best case only happens when every element of the tree is already sorted.

## Related questions

2 views
Problem: any ideas on what i need to do for this problem? what is the smallest possible depth of a leaf in a decision tree
45 views
Problems I am new in programming, can anyone give the right solution? In linear​ programming, choices available to a decision maker are called A. objectives. B. choice variables. C. decision variables. D. constraints.
5 views
Problem: I'll make a submission for a response to my question. Please, I have searched the internet but have not found any useful material, and I am now having trouble continuing my studies.
2 views
Problem: Quick sort is much better than merge sort in many cases. Though, when are the cases when merge sort might be a better solution than quick sort?
2 views
Problem: I'm having trouble finding a solution; could you please assist me &ldquo;What is the maximum bound for creating a red black tree insertion&rdquo;?
3 views
Problem: Please solve it &hellip; Because I am unable to find out the solution:
350 views
Problems: Can anyone give the right solution The decision structure that has two possible paths of execution is known as _____? a. Single alternative b. Double alternative c. Dual alternative d. Two alternative