X hits on this document

Powerpoint document

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

70 views

0 shares

0 downloads

0 comments

2 / 28

Comp 122

linsort - 2

Lin / Devi

Comp 122

Comparison-based Sorting

Comparison sort

»

Only comparison of pairs of elements may be used to gain order information about a sequence.

»

Hence, a lower bound on the number of comparisons will be a lower bound on the complexity of any comparison-based sorting algorithm.

All our sorts have been comparison sorts

The best worst-case complexity so far is(n lg n) (merge sort and heapsort).

We prove a lower bound of n lg n, (or (n lg n)) for any comparison sort, implying that merge sort and heapsort are optimal.

Document info
Document views70
Page views70
Page last viewedTue Dec 06 14:57:12 UTC 2016
Pages28
Paragraphs427
Words1924

Comments