Programming/Algorithms: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 12: | Line 12: | ||
|- | |- | ||
| Array || Θ(1) -> O(1) || Θ(n) -> O(n) || Θ(n) -> O(n) || Θ(n) -> O(n) || O(n) | | 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) | |||
|} | |} | ||
Revision as of 16:11, 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) |