DEV Community

loading...
Cover image for Big-O Cheatsheet to most common Data Structures and Sorting algorithms

Big-O Cheatsheet to most common Data Structures and Sorting algorithms

Rohith V
Full Stack Engineer || Java || Graduated From Government Engineerig College Thrissur. Interested in Data Structures in Java
・2 min read

Common data structure operations (Worst Case)

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 Linkedlist O(n) O(n) O(1) O(1)
Doubly Linkedlist O(n) O(n) O(1) O(1)
Hash Table N/A O(n) O(n) O(n)
Binary Search Tree O(n) O(n) O(n) O(n)

Sorting Algorithms

Best Case Avergae Case Worst Case Space Complexity
Quicksort nlogn nlogn n^2 logn
Mergesort nlogn nlogn nlogn n
Heapsort nlogn nlogn nlogn O(1)
Bubble sort n n^2 n^2 O(1)
Insertion sort n n^2 n^2 O(1)
Selection sort n^2 n^2 n^2 O(1)

Discussion (0)