X hits on this document

Powerpoint document

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

62 views

0 shares

0 downloads

0 comments

6 / 28

Comp 122

linsort - 6

Lin / Devi

Comp 122

A Lower Bound for Worst Case

Worst case no. of comparisons for a sorting algorithm is

»

Length of the longest path from root to any of the leaves in the decision tree for the algorithm.

Which is the height of its decision tree.

A lower bound on the running time of any comparison sort is given by

»

A lower bound on the heights of all decision trees in which each permutation appears as a reachable leaf.

Document info
Document views62
Page views62
Page last viewedSat Dec 03 15:34:21 UTC 2016
Pages28
Paragraphs427
Words1924

Comments