What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
n-1 if n is the no of elements. It happens when the input is already in sorted order. we compare element from 1 to n and tree follows the leftmost path in the decision tree.
No comments:
Post a Comment