Algorithms, part I Sumup

Now that the course is over, this a summary of the algorithms' performance seen in the lectures.

1.a.Quick-Union Algorithm

M union-find operations on N objects

QF	M*N
QU	M*N
Weighted QU	N + M*lg(N)
QU + path compression	N + M*lg(N)
Weighted QU + path compression	N + M*lg*(N)

Where lg* is the iterative 2-base logarithm:

N	lg*(N)
1	0
2	1
4	2
16	3
65536	4
pow(2, 65536)	5

1.b. Algorithm theory and Memory

We can assume the performance in time of an algorithm follows a linear rule on logarithms:

T(N) = a * pow(N, b) and lg(T(N)) = b * lg(N) + c

where b is the slope.

b represents system independent effects such as algorithm design and data input.

a represents system dependent effects like hardware, software, systems.

The 32-bits java data model specifies the following amount of memory distributed on:

data type	bytes
boolean	1
byte	1
char	2
int	4
float	4
long	8
double	8
char[]	2N + 24
int[]	4N + 24
double[]	8N + 24
object overhead	16
if inner class	8
reference	8
padding	multiple of 8

2. Sorting algorithms

sorting	inplace?	stable?	worst	average	best	remarks
selection	yes	no	pow(N,2)/2	pow(N,2)/2	pow(N,2)/2	N exchanges
insertion	yes	yes	pow(N,2)/2	pow(N,2)/4	N	small N or partially ordered arrays
shell (3x+1)	yes	no	?	?	N	subquadratic, tight code
merge	no	yes	NlgN	NlgN	NlgN	NlgN guarantee, stable
quick	yes	no	pow(N,2)/2	2NlgN	NlgN	faster in practice
3-way quick	yes	no	NlgN	2NlgN	N	improves quicksort in presence of duplicate keys
heapsort	yes	no	2NlgN	2NlgN	2NlgN	poor use of cache memory, inner loop longer than quicksort,not stable
?????	yes	yes	NlgN	NlgN	NlgN	holy sorting grail

3. Priority Queue and binary heap

Find largest M items in a steam of N items

implementation	time	space
sort	NlgN	N
elementary PQ	MN	M
binary heap	NlgM	M
best in theory	N	M

Any representation of a heap-ordered complete binary tree where keys in nodes and parent key no smaller than children's keys.

implementation	insert	del max	max
unordered array	1	N	N
ordered array	N	1	1
binary heap	lgN	lgN	1

4. Symbol Tables

	worst case			average
implementation	search	insert	delete	search	insert	delete	key interface
sequential search (unordered list)	N	N	N	N/2	N	N/2	equals
binary search (ordered array)	lgN	N	N	lgN	N/2	N/2	compareTo
BST	N	N	N	1.39lgN	1.39lgN	?	compareTo
2-3 tree	clgN	clgN	clgN	lgN	clgN	clgN	compareTo
red-black BST	2lgN	2lgN	2lgN	lgN	lgN	lgN	compareTo

5. Hash Tables

	worst case			average
implementation	search	insert	delete	search	insert	delete	key interface
separate chaining	lgN*	lgN*	lgN*	3-5*	3-5*	3-5*	equals
linear probing	lgN*	lgN*	lgN*	3-5*	3-5*	3-5*	equals

(*) under uniform hashing assumption