X hits on this document

Powerpoint document

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

71 views

0 shares

0 downloads

0 comments

8 / 28

Comp 122

linsort - 8

Lin / Devi

Comp 122

A Lower Bound for Worst Case

Proof:

From previous discussion, suffices to determine the height of a decision tree.

hheight, lno. of reachable leaves in a decision tree.

In a decision tree for n elements, l n!. Why?

In a binary tree of height h, no. of leaves l 2h. Prove it.

Hence,   n! l 2h.

Theorem 8.1:

Any comparison sort algorithm requires (n lg n) comparisons in the worst case.

Document info
Document views71
Page views71
Page last viewedWed Dec 07 11:05:47 UTC 2016
Pages28
Paragraphs427
Words1924

Comments