inline Complexity of Algorithms and Data-structures

Originally published on May 1st, 2020 (Last updated on May 1st, 2020)

The cheat-sheet of all search and sort algo­rithms and com­mon data-structures.

Data Struc­tures #

(Not a full list!)

Struc­tureMAX
Access
MAX
Search
MAX
Inser­tion
MAX
Dele­tion
AVG
Access
AVG
Search
AVG
Inser­tion
AVG
Dele­tion
Space-Com­plex­i­ty
ArrayO(1)O(n)O(n)O(n)O(1)O(n)O(n)O(n)O(n)
StackO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)
QueueO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)
Linked ListO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)
Hash TableN/AO(1)O(1)O(1)N/AO(n)O(n)O(n)O(n)

Sort­ing Algorithms #

(Not a full list!)

Algo­rithmWorstAver­ageBestSpace-Com­plex­i­ty
Quick­sortO(n log(n))O(n log(n))O(n^2)O(log n)
Merge­sortO(n log(n))O(n log(n))O(n log(n))O(n)
Heap­sortO(n log(n))O(n log(n))O(n log(n))O(1)

Comments

No com­ment sec­tion here 😄

You can reach me over at @knuth_dev or send me an Email.