Time Complexity is the amount of time taken by an algorithm for each of it's statement to complete the execution. As a result, it is highly dependent on the size of the processed data. It is helpful in defining an algorithm's effectiveness and evaluating its performance.
Space Complexity is the total amount of memory space taken by a program for it's execution. It includes storing input data and temporary values while execution of a program. Basically for variables, inputs, and outputs.
Auxiliary space + Input data space = Space ComplexityHere are all the time and space complexities listed below. Mainly Big-Oh (O) notation is used here for the representation.
Asymptotic notations are classified into three types:
1. Big-Oh (O) notation
2. Big Omega ( Ω ) notation
3. Big Theta ( Θ ) notationSorting & Searching:
Type of Sorting | Best Case | ​Average Case | Worst Case | Space Complexity |
Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
Merge Sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
Quick Sort | O(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) |
Bucket Sort | O(n+k) | O(n+k) | O(n^2) | O(n) |
Heap Sort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) |
Count Sort | O(n+k) | O(n+k) | O(n^2) | O(k) |
Tim Sort | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Shell Sort | O(n) | O((n log(n))^2) | O((n log(n))^2) | O(1) |
Tree Sort | O(n log(n)) | O(n log(n)) | O(n^2) | O(n) |
Cube Sort | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
Linear Search | O(1) | O(n) | O(n) | O(1) |
Binary Search | O(1) | O(log(n)) | O(log(n)) | O(1) |
Average Case Complexities :
Data Structure | Insertion | Deletion | Access | Search |
Array | O(n) | O(n) | O(1) | O(n) |
Stack | O(1) | O(1) | O(n) | O(n) |
Queue | O(1) | O(1) | O(n) | O(n) |
Singly Linked List | O(1) | O(1) | O(n) | O(n) |
Doubly Linked List | O(1) | O(1) | O(n) | O(n) |
Hash Table | O(1) | O(1) | O(1) | O(1) |
Binary Search Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
B- Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
Red-Black Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
AVL Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
Worst Case Complexities :
Data Structure | Insertion | Deletion | Access | Search | Space Complexity |
Array | O(n) | O(n) | O(1) | O(n) | O(n) |
Stack | O(1) | O(1) | O(n) | O(n) | O(n) |
Queue | O(1) | O(1) | O(n) | O(n) | O(n) |
Singly Linked List | O(1) | O(1) | O(n) | O(n) | O(n) |
Doubly Linked List | O(1) | O(1) | O(n) | O(n) | O(n) |
Hash Table | O(n) | O(n) | O(n) | O(n) | O(n) |
Binary Search Tree | O(n) | O(n) | O(n) | O(n) | O(n) |
B-Tree | O(n) | O(n) | O(n) | O(n) | O(n) |
Red-Black Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
AVL Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
Comments