X hits on this document

Powerpoint document

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

60 views

0 shares

0 downloads

0 comments

12 / 28

Comp 122

linsort - 12

Lin / Devi

Comp 122

Algorithm Analysis

The overall time is O(n+k).  When we have k=O(n), the worst case is O(n).

»

for-loop of lines 1-2 takes time O(k)

»

for-loop of lines 3-4 takes time O(n)

»

for-loop of lines 5-6 takes time O(k)

»

for-loop of lines 7-9 takes time O(n)

Stable, but not in place.

No comparisons made: it uses actual values of the elements to index into an array.

Document info
Document views60
Page views60
Page last viewedSat Dec 03 03:02:01 UTC 2016
Pages28
Paragraphs427
Words1924

Comments