X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 5 / 28

106 views

0 shares

0 downloads

0 comments

5 / 28

Comp 122

linsort - 5

Lin / Devi

Comp 122

Decision Tree (Contd.)

Execution of sorting algorithm corresponds to tracing a path from root to leaf.

The tree models all possible execution traces.

At each internal node, a comparison ai aj is made.

»

If ai aj, follow left subtree, else follow right subtree.

»

View the tree as if the algorithm splits in two at each node, based on information it has determined up to that point.

When we come to a leaf, ordering a(1) a (2) a (n) is established.

A correct sorting algorithm must be able to produce any permutation of its input.

»

Hence, each of the n! permutations must appear at one or more of the leaves of the decision tree.

Document info
Document views106
Page views106
Page last viewedMon Jan 23 14:59:42 UTC 2017
Pages28
Paragraphs427
Words1924

Comments