Self – balancing binary search trees have a much better average-case time complexity than hash tables.

Category: QuestionsSelf – balancing binary search trees have a much better average-case time complexity than hash tables.
Editor">Editor Staff asked 1 month ago

Self – balancing binary search trees have a much better average-case time complexity than hash tables.
 
(a) True
 
(b) False
 
My question is taken from Binary Trees in chapter Binary Trees of Data Structures & Algorithms I
 
This question was posed to me in class test.

1 Answers
Editor">Editor Staff answered 1 month ago

Correct choice is (b) False
 
Easy explanation – For lookup, insertion and deletion hash table take O(1) time in average-case while self – balancing binary search trees takes O(log n). Therefore, hash tables perform better in average-case.