What is the smallest possible depth of a leaf in a decision tree for a compariso

jeseHainsij

jeseHainsij

Answered question

2021-11-18

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

Answer & Explanation

Stephanie Mann

Stephanie Mann

Beginner2021-11-19Added 25 answers

Assume that there are n elements in our array. This indicates that the possible arrangements for an array are n! permutations. Although all of the leaves in a decision tree must be the same height, they are not always.
For example take consider an array of numbers: 7, 10, 1, 12, 14 
When algorithm starts comparing it compares 7 and 10. Obviously, 10is larger than 7. Next, we compare 11 and 10. 11 is larger than 10. We don't need to compare 11 and 7 because transitive properties hold: if b>a and c>b then c>a. This means that we will perform only n-1 comparisons which yields depth of n. 
When an array isnt

Gloria Lusk

Gloria Lusk

Beginner2021-11-20Added 18 answers

n-1 for an input array of length n. 
In a decision tree, each internal node is annotated by i:j for some i and j in the range 1i,jn, where n is the no of elements in the input sequence. 
The absolute best case happens for a path in decision tree, in which, for each node i:j there is no other node i:k or k:j in the path for some k in {1,2,3,.n}{i,j}
The length of the path, thus, will be n-1. 
Example :- decision tree for insertion sort being implemented on a sorted array.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?