Data Structures Time and Space Complexity Flashcards
(14 cards)
What is the average to worst time complexity for array access, search, insertion, and deletion? What is the worst space complexity?
Access = O(1) - O(1) Search = O(n) - O(n) Insertion = O(n) - O(n) Deletion = O(n) - O(n) Space = O(n)
What is the average to worst time complexity for stack access, search, insertion, and deletion? What is the worst space complexity?
Access = O(n) - O(n) Search = O(n) - O(n) Insertion = O(1) - O(1) Deletion = O(1) - O(1) Space = O(n)
What is the average to worst time complexity for queue access, insertion, search, and deletion? What is the worst space complexity?
Access = O(n) - O(n) Search = O(n) - O(n) Insertion = O(1) - O(1) Deletion = O(1) - O(1) Space = O(n)
What is the average to worst time complexity for single-linked list access, insertion, search, and deletion? What is the worst space complexity?
Access = O(n) - O(n) Search = O(n) - O(n) Insertion = O(1) - O(1) Deletion = O(1) - O(1) Space = O(n)
What is the average to worst time complexity for double-linked list access, insertion, search, and deletion? What is the worst space complexity?
Access = O(n) - O(n) Search = O(n) - O(n) Insertion = O(1) - O(1) Deletion = O(1) - O(1) Space = O(n)
What is the average to worst time complexity for skip list access, insertion, search, and deletion? What is the worst space complexity?
Access = O(log n) - O(n) Search = O(log n) - O(n) Insertion = O(log n) - O(n) Deletion = O(log n) - O(n) Space = O(n log n)
What is the average to worst time complexity for binary search tree access, insertion, search, and deletion? What is the worst space complexity?
Access = O(log n) - O(n) Seach = O(log n) - O(n) Insertion = O(log n) - O(n) Deletion = O(log n) - O(n) Space = O(n)
What is the average to worst time complexity for Cartesian tree access, insertion, search, and deletion? What is the worst space complexity?
Access = N/A Seach = O(log n) - O(n) Insertion = O(log n) - O(n) Deletion = O(log n) - O(n) Space = O(n)
What is the average to worst time complexity for B-tree access, insertion, search, and deletion? What is the worst space complexity?
Access = O(log n) - O(log n) Seach = O(log n) - O(log n) Insertion = O(log n) - O(log n) Deletion = O(log n) - O(log n) Space = O(n)
What is the average to worst time complexity for red-black tree access, insertion, search, and deletion? What is the worst space complexity?
Access = O(log n) - O(log n) Seach = O(log n) - O(log n) Insertion = O(log n) - O(log n) Deletion = O(log n) - O(log n) Space = O(n)
What is the average to worst time complexity for splay tree access, insertion, search, and deletion? What is the worst space complexity?
Access = N/A Seach = O(log n) - O(log n) Insertion = O(log n) - O(log n) Deletion = O(log n) - O(log n) Space = O(n)
What is the average to worst time complexity for AVL tree access, insertion, search, and deletion? What is the worst space complexity?
Access = O(log n) - O(log n) Seach = O(log n) - O(log n) Insertion = O(log n) - O(log n) Deletion = O(log n) - O(log n) Space = O(n)
What is the average to worst time complexity for KD tree access, insertion, search, and deletion? What is the worst space complexity?
Access = O(log n) - O(log n) Seach = O(log n) - O(log n) Insertion = O(log n) - O(log n) Deletion = O(log n) - O(log n) Space = O(n)
What is the average to worst time complexity for hash table access, insertion, search, and deletion? What is the worst space complexity?
Access = N/A Seach = O(1) - O(n) Insertion = O(1) - O(n) Deletion = O(1) - O(n) Space = O(n)