Programming/Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
|+ Data Structure Operations | |+ Data Structure Operations | ||
|- | |- | ||
! rowspan="3"| Data Structure !! colspan="4"| Time Complexity !! rowspan="3"| Space Complexity | ! rowspan="3"| Data Structure !! colspan="4"| Time Complexity !! rowspan="3"| Space Complexity !! rowspan="3"| Notes | ||
|- | |- | ||
! colspan="4"|Average -> Worst | ! colspan="4"|Average -> Worst | ||
| Line 25: | Line 25: | ||
| Binary Search Tree || Θ(log(n)) -> O(n) || Θ(log(n)) -> O(n) || Θ(log(n)) -> O(n) || Θ(log(n)) -> O(n) || O(n) | | Binary Search Tree || Θ(log(n)) -> O(n) || Θ(log(n)) -> O(n) || Θ(log(n)) -> O(n) || Θ(log(n)) -> O(n) || O(n) | ||
|- | |- | ||
| B Tree || Θ(log(n)) -> O(log(n)) || Θ(log(n)) -> O(log(n)) || Θ(log(n)) -> O(log(n)) || Θ(log(n)) -> O(log(n)) || O(n) | | B Tree || Θ(log(n)) -> O(log(n)) || Θ(log(n)) -> O(log(n)) || Θ(log(n)) -> O(log(n)) || Θ(log(n)) -> O(log(n)) || O(n) || Self-balancing | ||
|} | |||
{| class="wikitable" | |||
|+ Array Sorting Algorithms | |||
|- | |||
! rowspan="2"| Data Structure !! colspan="3"| Time Complexity !! rowspan="2"| Space Complexity !! rowspan="3"| Notes | |||
|- | |||
! Best !! Average !! Worst | |||
|- | |||
| Bubble Sort || Ω(n) || Θ(n^2) || O(n^2) || O(1) | |||
|- | |||
| Quicksort || Ω(n log(n)) || Θ(n log(n)) || O(n^2) || O(log(n)) | |||
|- | |||
| Mergesort || Ω(n log(n)) || Θ(n log(n)) || O(n log(n)) || O(n) | |||
|- | |||
| Insertion Sort || Ω(n) || Θ(n^2) || O(n^2) || O(1) | |||
|- | |||
| Timsort || Ω(n) || Θ(n log(n)) || O(n log(n)) || O(n) || Combination of Mergesort and Insertion Sort made for Python | |||
|- | |||
| Heapsort || Ω(n log(n)) || Θ(n log(n)) || O(n log(n)) || O(1) | |||
|} | |} | ||
Revision as of 16:22, 18 January 2023
Adapted from: https://www.bigocheatsheet.com/
| Data Structure | Time Complexity | Space Complexity | Notes | |||
|---|---|---|---|---|---|---|
| Average -> Worst | ||||||
| Access | Search | Insertion | Deletion | |||
| Array | Θ(1) -> O(1) | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(n) -> O(n) | O(n) | |
| Stack | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Queue | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Linked List | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Double Linked List | Θ(n) -> O(n) | Θ(n) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Hash Table | N/A | Θ(1) -> O(n) | Θ(1) -> O(n) | Θ(1) -> O(n) | O(n) | |
| Binary Search Tree | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | Θ(log(n)) -> O(n) | O(n) | |
| B Tree | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | Θ(log(n)) -> O(log(n)) | O(n) | Self-balancing |
| Data Structure | Time Complexity | Space Complexity | Notes | ||
|---|---|---|---|---|---|
| Best | Average | Worst | |||
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |
| Quicksort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) | |
| Mergesort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) | |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) | |
| Timsort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) | Combination of Mergesort and Insertion Sort made for Python |
| Heapsort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) | |