For the following symbol table implementations, unordered linked list, ordered a

Question

For the following symbol table implementations, unordered linked list, ordered array, binary search tree (BST), red-black BST, hashing with separate chaining, hashing with linear probing

1) Which one(s) can have constant running time for search and insertion in average-case?

2) Which one(s) has (have) O(logN) running time for insertion in average-case?

3) which one(s) has (have) o(N) running time for search in worst-case?

4) which one(s) has (have) O(N) running time for insertion in worst-case?

5) Which one(s) can support order symbol table efficiently?

Explanation / Answer

1) Which one(s) can have constant running time for search and insertion in average-case?

Ans: Hashing with linear probing, Red Black BTS

2) Which one(s) has (have) O(logN) running time for insertion in average-case?

Ans: Binary Search Tree and Red-Black BST

3) which one(s) has (have) o(N) running time for search in worst-case?

ANs: BST and unordered linked list.

4) which one(s) has (have) O(N) running time for insertion in worst-case?

Ans: Ordered Array, BST and Orderd linked list.

5) Which one(s) can support order symbol table efficiently?

Ans: Red-Black Tree, Ordered Array and Binary Search Tree.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.