X hits on this document

Powerpoint document

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

108 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 views108
Page views108
Page last viewedTue Jan 24 09:21:25 UTC 2017
Pages28
Paragraphs427
Words1924

Comments