Data Structures Time and Space Complexity

Question 1

What is the average to worst time complexity for array access, search, insertion, and deletion? What is the worst space complexity?

Answer 1

Access = O(1) - O(1)
Search = O(n) - O(n)
Insertion = O(n) - O(n)
Deletion = O(n) - O(n)
Space = O(n)

Question 2

What is the average to worst time complexity for stack access, search, insertion, and deletion? What is the worst space complexity?

Answer 2

Access = O(n) - O(n)
Search = O(n) - O(n)
Insertion = O(1) - O(1)
Deletion = O(1) - O(1)
Space = O(n)

Question 3

What is the average to worst time complexity for queue access, insertion, search, and deletion? What is the worst space complexity?

Answer 3

Access = O(n) - O(n)
Search = O(n) - O(n)
Insertion = O(1) - O(1)
Deletion = O(1) - O(1)
Space = O(n)

Question 4

What is the average to worst time complexity for single-linked list access, insertion, search, and deletion? What is the worst space complexity?

Answer 4

Access = O(n) - O(n)
Search = O(n) - O(n)
Insertion = O(1) - O(1)
Deletion = O(1) - O(1)
Space = O(n)

Question 5

What is the average to worst time complexity for double-linked list access, insertion, search, and deletion? What is the worst space complexity?

Answer 5

Access = O(n) - O(n)
Search = O(n) - O(n)
Insertion = O(1) - O(1)
Deletion = O(1) - O(1)
Space = O(n)

Question 6

What is the average to worst time complexity for skip list access, insertion, search, and deletion? What is the worst space complexity?

Answer 6

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)

Question 7

What is the average to worst time complexity for binary search tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 7

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)

Question 8

What is the average to worst time complexity for Cartesian tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 8

Access = N/A
Seach = O(log n) - O(n)
Insertion = O(log n) - O(n)
Deletion = O(log n) - O(n)
Space = O(n)

Question 9

What is the average to worst time complexity for B-tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 9

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)

Question 10

What is the average to worst time complexity for red-black tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 10

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)

Question 11

What is the average to worst time complexity for splay tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 11

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)

Question 12

What is the average to worst time complexity for AVL tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 12

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)

Question 13

What is the average to worst time complexity for KD tree access, insertion, search, and deletion? What is the worst space complexity?

Answer 13

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)

Question 14

What is the average to worst time complexity for hash table access, insertion, search, and deletion? What is the worst space complexity?

Answer 14

Access = N/A
Seach = O(1) - O(n)
Insertion = O(1) - O(n)
Deletion = O(1) - O(n)
Space = O(n)