X hits on this document

Powerpoint document

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

79 views

0 shares

0 downloads

0 comments

23 / 28

Comp 122

linsort - 23

Lin / Devi

Comp 122

Analysis

Relies on no bucket getting too many values.

All lines except insertion sorting in line 5 take O(n) altogether.

Intuitively, if each bucket gets a constant number of elements, it takes O(1) time to sort each bucket O(n) sort time for all buckets.

We “expect” each bucket to have few elements, since the average is 1 element per bucket.

But we need to do a careful analysis.

Document info
Document views79
Page views79
Page last viewedSat Dec 10 20:59:18 UTC 2016
Pages28
Paragraphs427
Words1924

Comments