X hits on this document

Powerpoint document

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

74 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 views74
Page views74
Page last viewedWed Dec 07 20:47:28 UTC 2016
Pages28
Paragraphs427
Words1924

Comments