Programming/Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 24: | Line 24: | ||
|- | |- | ||
| 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) | |||
|} | |} | ||
Revision as of 16:13, 18 January 2023
Adapted from: https://www.bigocheatsheet.com/
| Data Structure | Time Complexity | Space Complexity | |||
|---|---|---|---|---|---|
| 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) |