Complexity of algorithms

📅   03. 08. 2021
👤   Jan Barášek

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 n2 n2 1 Yes
Insertion sort n n2 n2 1
Selection sort n2 n2 n2 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) n2 log(n) No
Shell sort n log(n) depends on the sequence n (log(n))2 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     More about the author

The author works as a senior developer and software architect in Prague (Czech republic, Europe). He designs and manages large web applications that you know and use. Since 2009 he has gained a wealth of experience which he passes on through this website.

I'd be happy to help: