Know Thy Complexities!

Hi there! This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science. When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.

`Good`	`Fair`	`Poor`

Searching

Algorithm	Data Structure	Time Complexity		Space Complexity
		Average	Worst	Worst
Depth First Search (DFS)	Graph of \|V\| vertices and \|E\| edges	`-`	`O(\|E\| + \|V\|)`	`O(\|V\|)`
Breadth First Search (BFS)	Graph of \|V\| vertices and \|E\| edges	`-`	`O(\|E\| + \|V\|)`	`O(\|V\|)`
Binary search	Sorted array of n elements	`O(log(n))`	`O(log(n))`	`O(1)`
Linear (Brute Force)	Array	`O(n)`	`O(n)`	`O(1)`
Shortest path by Dijkstra, using a Min-heap as priority queue	Graph with \|V\| vertices and \|E\| edges	`O((\|V\| + \|E\|) log \|V\|)`	`O((\|V\| + \|E\|) log \|V\|)`	`O(\|V\|)`
Shortest path by Dijkstra, using an unsorted array as priority queue	Graph with \|V\| vertices and \|E\| edges	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(\|V\|)`
Shortest path by Bellman-Ford	Graph with \|V\| vertices and \|E\| edges	`O(\|V\|\|E\|)`	`O(\|V\|\|E\|)`	`O(\|V\|)`

Sorting

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	`O(n log(n))`	`O(n log(n))`	`O(n^2)`	`O(n)`
Mergesort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Select Sort	Array	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Bucket Sort	Array	`O(n+k)`	`O(n+k)`	`O(n^2)`	`O(nk)`
Radix Sort	Array	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`

Data Structures

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Indexing	Search	Insertion	Deletion	Indexing	Search	Insertion	Deletion
Basic Array	`O(1)`	`O(n)`	`-`	`-`	`O(1)`	`O(n)`	`-`	`-`	`O(n)`
Dynamic Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Singly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Doubly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Skip List	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n log(n))`
Hash Table	`-`	`O(1)`	`O(1)`	`O(1)`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Binary Search Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Cartresian Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
B-Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Red-Black Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
Splay Tree	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
AVL Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`

Heaps

Heaps	Time Complexity
	Heapify	Find Max	Extract Max	Increase Key	Insert	Delete	Merge
Linked List (sorted)	`-`	`O(1)`	`O(1)`	`O(n)`	`O(n)`	`O(1)`	`O(m+n)`
Linked List (unsorted)	`-`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(1)`	`O(1)`
Binary Heap	`O(n)`	`O(1)`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(m+n)`
Binomial Heap	`-`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`
Fibonacci Heap	`-`	`O(1)`	`O(log(n))*`	`O(1)*`	`O(1)`	`O(log(n))*`	`O(1)`

Graphs

Node / Edge Management	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
Adjacency list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|V\| + \|E\|)`	`O(\|E\|)`	`O(\|V\|)`
Incidence list	`O(\|V\|+\|E\|)`	`O(1)`	`O(1)`	`O(\|E\|)`	`O(\|E\|)`	`O(\|E\|)`
Adjacency matrix	`O(\|V\|^2)`	`O(\|V\|^2)`	`O(1)`	`O(\|V\|^2)`	`O(1)`	`O(1)`
Incidence matrix	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|V\| ⋅ \|E\|)`	`O(\|E\|)`

Notation for asymptotic growth

letter	bound	growth
(theta) Θ	upper and lower, tight[1]	equal[2]
(big-oh) O	upper, tightness unknown	less than or equal[3]
(small-oh) o	upper, not tight	less than
(big omega) Ω	lower, tightness unknown	greater than or equal
(small omega) ω	lower, not tight	greater than

[1] Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n).SO

[2] f(x)=Θ(g(n)) means f (the running time of the algorithm) grows exactly like g when n (input size) gets larger. In other words, the growth rate of f(x) is asymptotically proportional to g(n).

[3] Same thing. Here the growth rate is no faster than g(n). big-oh is the most useful because represents the worst-case behavior.

In short, if algorithm is __ then its performance is __

algorithm	performance
o(n)	< n
O(n)	≤ n
Θ(n)	= n
Ω(n)	≥ n
ω(n)	> n

Saturday, January 1, 2005

Garbage collector(s)

Garbage collector can be generational or single spaced with a parallel or a concurrent mark and a parallel sweep or a concurrent sweep.
Generational garbage collection – In this case the heap is divided into two sections: an old generation and a young generation (nursery). Initially objects are allocated in the nursery and when it is full, live objects are promoted to the old generation. For this operation the collector has to stop the Java threads.
Single-spaced garbage collection – All objects live in a single space on the heap, regardless of their age.
Concurrent mark and sweep algorithm – The concurrent garbage collection algorithm does its marking and sweeping concurrently with all other processing, i.e., the Java threads are not stopped during garbage collection.
allel garbage collection mark and sweep algorithm – The parallel garbage collection algorithm stops Java threads when the heap is full and uses all available CPUs to perform a mark and sweep of the heap. Typically a parallel collection has longer pause times than a concurrent collection, but maximizes the application throughput.

We can select a specific garbage collector by using -Xgc:<option>, with option being one of the following:

singlecon – Single-space, concurrent garbage collection. This mode reduces application throughput but keeps pause times to a minimum.
gencon – Generational, concurrent garbage collection. The gencon mode is better than the singlecon mode for applications that allocate lots of short-lived objects. This mode reduces application throughput but keeps pause times to a minimum.
singlepar – Single-space, parallel garbage collection. This mode increases pause times when compared with the concurrent mode but maximizes throughput.
genpar – Generational, parallel garbage collection. This mode is generally better than the singlepar mode for applications that allocate lots of short-lived objects. In this mode, a higher number of garbage collections are performed than in the singlepar mode, but the individual pause times are shorter, resulting in lower fragmentation in the old generation space.
genconpar – Generational garbage collection. Sets the garbage collection mode to generational with a concurrent mark algorithm and a parallel sweep algorithm.
genparcon – Generational garbage collection. Sets the garbage collection mode to generational with a parallel mark algorithm and a concurrent sweep algorithm.
singleconpar – Single-space garbage collection. Sets the garbage collection mode to single-spaced with a concurrent mark algorithm and a parallel sweep algorithm.
singleparcon – Single-space garbage collection. Sets the garbage collection mode to single-spaced with a parallel mark and a concurrent sweep algorithm.
throughput – The garbage collector is optimized for application throughput. This means that the garbage collector works as effectively as possible, giving as much CPU resources to the Java threads as possible. This might, however, cause non-deterministic pauses when the garbage collector stops all Java threads for garbage collection.
pausetime – The garbage collector is optimized for short pauses. This means that the garbage collection works concurrently with the Java application when necessary, in order to avoid pausing the Java threads. This inflicts a slight performance overhead to the application, as the concurrent garbage collector demands more system resources (CPU time and memory) than the parallel garbage collector that is used for optimal throughput. The target pause time is by default 200 milliseconds, which can be changed by using -XpauseTarget.
deterministic – Optimizes the garbage collector for very short and deterministic pause times. The garbage collector tries to keep the garbage collection pauses below a given pause target. The performance depends on the application and the hardware. Running on slower hardware, with a different heap size or with a large amount of live data can break the deterministic behavior or cause performance degradation over time; faster hardware or a less amount of live data might allows us to set a lower pause target. The pause target for the deterministic mode is by default 30 milliseconds, which can be changed by using -XpauseTarget