CSC Interview Question
Software AnalystsCountry: India
Interview Type: Written Test
Why would a Binary Tree have O(1) if no sort order is maintained?
Also, for hash table with collision, it is O(1 + alpha)
And if your alpha is large, then you don't get O(1)
alpha is the load factor - i.e. the ratio of number of elements to be stored and number of slots in the hash table.
a) O(n^2)
- JustCoding October 10, 2012b) O(n)
c) O(n) if no sort order maintained; O(log n) if it is BST or sorted tree
d) O(1)
e) O(n) if it is unsorted; O(log n) if sorted