need a quick reminder of algorithm complexity basics (easy one for college guys)

[andersod2]

Hey can anybody remind me of the following things which I have forgotten since I took Algorithm Analysis (about 10 years ago!) ...

(1) advantages/disadvantages of linked lists (for insertion and search)
(2) " " " of contiguous array
(3) " " " of associative array (i.e. map / hash)


I also need a brief reminder of how the following algorithms work, and their advantages/ disadvantages....thanks for any input!

quick sort
heap sort
insertion sort
merge sort
quick bucket sort
shell sort

[Zachm]

Very very briefly:

(1) advantages/disadvantages of linked lists (for insertion and search)

Insertion to front / back is O(1), search is O(n).


(2) " " " of contiguous array

Insertion to a sorted array can be O(n) - may need to reallocate larger memory size for the array. Search in a sorted array is O(log n).


(3) " " " of associative array (i.e. map / hash)

Map - depends on implementation - may be binary tree, balanced tree etc.
Hash table - Disadvantage - requires extra space allocation in advance. Advantage - fast insertion extraction based on how good the hash function is and on the table size (larger table --> lesser chance of need to rehash).


I also need a brief reminder of how the following algorithms work, and their advantages/ disadvantages....thanks for any input!

quick sort
heap sort
insertion sort
merge sort
quick bucket sort
shell sort

A VERY quick google search on each of the above will yield your answers.

Regards,
Zachm