Complexities

Оператор сравнения асимптотических оценок	Оператор сравнения чисел
Алгоритм является o( что-то )	Число < чего-то
Алгоритм является O( что-то )	Число <= чего-то
Алгоритм является Θ( что-то )	Число = чего-то
Алгоритм является Ω( что-то )	Число >= чего-то
Алгоритм является ω( что-то )	Число > чего-то

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)

Data structures

Data Structure	Time Complexity								Space Complexity
	Average				Worst				Worst
	Access	Search	Insertion	Deletion	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	O(n)
Queue	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)	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	N/A	O(1)	O(1)	O(1)	N/A	O(n)	O(n)	O(n)	O(n)
Binary Search Tree	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(n)	O(n)	O(n)	O(n)	O(n)
Red-Black Tree	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)
B-Tree	Θ(log(n))	Θ(log(n))	Θ(log(n))	Θ(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)

References

1. Введение в анализ сложности алгоритмов (часть 1). Available at: https://habrahabr.ru/post/196560
2. Введение в анализ сложности алгоритмов (часть 2). Available at: https://habrahabr.ru/post/195482/
3. Введение в анализ сложности алгоритмов (часть 3). Available at: https://habrahabr.ru/post/195996/
4. Введение в анализ сложности алгоритмов (часть 4). Available at: https://habrahabr.ru/post/196226/
5. Big-O Algorithm Complexity Cheat Sheet. Available at: http://bigocheatsheet.com
6. Знай сложности алгоритмов. Available at: https://habrahabr.ru/post/188010
7. Оценка сложности алгоритмов. Available at: https://habrahabr.ru/post/104219