Decision-tree model a decision tree can model the execution of any comparison sort. One tree for each input size n View the algorithm as splitting whenever it compares two elements The tree contains the comparisons along all possible instruction traces The running time of the algorithm =the length of the path taken Worst-case running time=height of tree o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.8© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.8 Decision-tree model A decision tree can model the execution of any comparison sort: • One tree for each input size n. • View the algorithm as splitting whenever it compares two elements. • The tree contains the comparisons along all possible instruction traces. • The running time of the algorithm = the length of the path taken. • Worst-case running time = height of tree