In the problem statement there is a question. "Is it possiblr to sort in O(n)/time if ties are to be broken on the name field?"
I dont’t understand the question, more exactly the breaking ties part.
(Java) 14.3 V1 question
daemoohn
#1
0 Likes
adnanaziz
#2
if you are sorting an array of people by age (which is an integer, between 0 and 200) and you dont care about ties, you can sort in O(n) time using a map from ages to people (like the book example).
however, if you want to break ties by name, it’s no longer possible to do O(n) sort - suppose all ages were same, then basically you have to sort on name, which requires O(n log n) comparisons.
0 Likes
daemoohn
#3
Oh, I got it! I’m not a native English speaker and “ties” didn’t ring “equality” in my brain, just “connections”. So sorry…
0 Likes