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 Which one(s) can have constant running time for search and insertion in average-case? Which one(s) has (have) O(logN) running time for insertion in average-case? Which one(s) has (have) O(N) running time for search in worst-case? Which one(s) has (have) O(N) running time for insertion in worst-case? Which one(s) can support order symbol table efficiently?

Explanation / Answer

1) hashing

2)Bst

3) unordered array and bst(skew)

4) hashing (chaining in worst case we might have to travel entire list)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---