BSc Docs

ADS Big O Cheatsheet

7 min read · tagged ads, en

Contents

Source: http://bigocheatsheet.com/

Common Datastructure Operations

Data Structure	Time Complexity
	Average
	Access	Search	Insertion	Deletion
Array	`Θ(1)`	`Θ(n)`	`Θ(n)`	`Θ(n)`
Stack	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`
Queue	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`
Singly-Linked List	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`
Doubly-Linked List	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`
Skip List	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`
Hash Table	`N/A`	`Θ(1)`	`Θ(1)`	`Θ(1)`
Binary Search Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`
Cartesian Tree	`N/A`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`
B-Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`
Red-Black Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`
Splay Tree	`N/A`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`
AVL Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`
KD Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`

Data Structure	Time Complexity
	Worst
	Access	Search	Insertion	Deletion
Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`
Stack	`O(n)`	`O(n)`	`O(1)`	`O(1)`
Queue	`O(n)`	`O(n)`	`O(1)`	`O(1)`
Singly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`
Doubly-Linked List	`O(n)`	`O(n)`	`O(1)`	`O(1)`
Skip List	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Hash Table	`N/A`	`O(n)`	`O(n)`	`O(n)`
Binary Search Tree	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Cartesian Tree	`N/A`	`O(n)`	`O(n)`	`O(n)`
B-Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`
Red-Black Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`
Splay Tree	`N/A`	`O(log(n))`	`O(log(n))`	`O(log(n))`
AVL Tree	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`
KD Tree	`O(n)`	`O(n)`	`O(n)`	`O(n)`

Space Complexity: Alles $O(n)$ ausser Skip List ist $O(nlog(n))$

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(log(n))`
Mergesort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Timsort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Selection Sort	`Ω(n^2)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tree Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(n)`
Shell Sort	`Ω(n log(n))`	`Θ(n(log(n))^2)`	`O(n(log(n))^2)`	`O(1)`
Bucket Sort	`Ω(n+k)`	`Θ(n+k)`	`O(n^2)`	`O(n)`
Radix Sort	`Ω(nk)`	`Θ(nk)`	`O(nk)`	`O(n+k)`
Counting Sort	`Ω(n+k)`	`Θ(n+k)`	`O(n+k)`	`O(k)`
Cubesort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`

Simon Anliker Someone has to write all this stuff.

About the author.