CODEWITHSUNDEEP
algorithmsortingtreedepth
Kamil Gosciminski
Kamil Gosciminski

Reputation: 17177

Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)

What is the shortest possible depth of a leaf in decision tree refering to comparison sorting algorithm ?

Does it change depending on the alogrithm?

Upvotes: 6

Views: 10020

Answers (2)

Sujoy Roy
Sujoy Roy

Reputation: 119

To see this consider a graph of n nodes, each node i representing A[i]. Draw a (directed) edge from i to j 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. Hence we have two components C1 and C2 and we know nothing about the relative order of array elements indexed by C1 against elements indexed by C2. therefore there cannot be a single permutation π that sorts all inputs passing these k tests - so π() is wrong for some arrays which lead to leaf

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55619

The absolute best case happens when we just check every element and see that the data's already sorted.

This will result in n-1 comparisons and thus the leaf will have a depth of n-1.

Practically, this happens for insertion sort (which isn't all that good otherwise though).

Does it change depending on the algorithm?

Absolutely. The best case of an algorithm is a good indicator - the shortest depth for one with O(n log n) best case would be longer than the shortest depth for one with O(n) best case.

Upvotes: 8

Related Questions