Complexity of algorithms

03. 08. 2021

Obsah článku

Each algorithm has its own complexity, which can be expressed in mathematical notation. This overview shows the typical complexity of algorithms according to the size of the input data (i.e. the number of elements they work with) and which types of algorithms are suitable for which type of task.

In general, there is a best specialized algorithm for each type of problem. No algorithm is universally best, and you always need to know your context.

Big O Notation

The Big O Notation is used to classify algorithms according to how their runtime or memory requirements increase with increasing input size.

The following chart shows the most common growth orders of algorithms specified in Big O Notation.

Below is a list of some of the most commonly used Big O notations and a comparison of their performance with respect to different input data sizes.

Big O Notation	Complexity for 10 elements	Complexity for 100 elements	Complexity for 1000 elements
O(1)	1	1	1
O(log N)	3	6	9
O(N)	10	100	1000
O(N log N)	30	600	9000
O(N^2)	100	10000	1000000
O(2^N)	1024	1.26e+29	1.07e+301
O(N!)	3628800	9.3e+157	4.02e+2567

Complexity of data structure operations

Data Structure	Access	Search	Insert	Remove	Comment
Array	1	n	n	n	n
Stack	n	n	n	1	1
Queue	n	n	n	1
Linked List	n	n	n	1	n
Hash Table	-	n	n	n	n
Binary Search Tree	n	n	n	n	In the case of a balanced tree, the complexity will be O(log(n)).
B-Tree	log(n)	log(n)	log(n)	log(n)	log(n)
Red-Black Tree	log(n)	log(n)	log(n)	log(n)
AVL Tree	log(n)	log(n)	log(n)	log(n)	log(n)
Bloom Filter	-	1	1	-	When searching for `false positives`

Complexity of sorting algorithms

Algorithm Name	Best	Average	Worst	Memory	Stable?	Comment
Bubble sort	n	n²	n²	1	Yes
Insertion sort	n	n²	n²	1
Selection sort	n²	n²	n²	1
Heap sort	n log(n)	n log(n)	n log(n)	1		No
Merge sort	n log(n)	n log(n)	n log(n)	n	Yes
	Quick sort	n log(n)	n log(n)	n²	log(n)	No
Shell sort	n log(n)	depends on the sequence	n (log(n))²	1		No
Counting sort	n + r	n + r	n + r	n + r	Yes	r - the largest number in the array
Radix sort	n * k	n * k	n * k	n + k	Yes	k - length of the longest key

Jan Barášek Více o autorovi

Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.

Rád vám pomůžu: