Shasoosh Posted November 12, 2009 Share Posted November 12, 2009 There's an Hash table T[1..m] n series with key numbers (k1,k2,k3...kn) and an Hash function of some sort: h we'll insert the n keys into the hash table with the h function (with stringing in case of a collision) we'll use merge sort on the linked lists we'll concatenate the linked lists in the T cell order 1.what's the Average case performance? 2.what's the worst case performance? 3. do you think that in any case we'll get a sorting of the keys (k1,k2,k3...kn)? if not, in which case we will get a sorted series? thanks Link to comment Share on other sites More sharing options...
0 Andre S. Veteran Posted November 12, 2009 Veteran Share Posted November 12, 2009 So... you expect anyone here to actually give you the answers? Read your manual and try to figure it out, that's the point of the class. Link to comment Share on other sites More sharing options...
0 Shasoosh Posted November 12, 2009 Author Share Posted November 12, 2009 I got the answers 1. O(n) 2. O(n^2) but i didn't understand 2, from what i understand it should be O(nlogn) Link to comment Share on other sites More sharing options...
Question
Shasoosh
There's an Hash table T[1..m]
n series with key numbers (k1,k2,k3...kn)
and an Hash function of some sort: h
we'll insert the n keys into the hash table with the h function (with stringing in case of a collision)
we'll use merge sort on the linked lists
we'll concatenate the linked lists in the T cell order
1.what's the Average case performance?
2.what's the worst case performance?
3. do you think that in any case we'll get a sorting of the keys (k1,k2,k3...kn)?
if not, in which case we will get a sorted series?
thanks
Link to comment
Share on other sites
2 answers to this question
Recommended Posts