Re:Twitter Sort
by blt on Wednesday January 14, 2015 @06:16AM
(#8885562)
give me a break, it does O(n^2) work to verify that the response is sorted and contains the same values.
[ Parent
| on HN ]
This can be improved. The following should be sufficient:
1. check that the list is the same size
2. for every element in the original, do a binary search in the new list; fail if not found
3. check that the element following the element you found is greater than it
This should make it run in the time it takes to do a binary search times the list size, or O(n * log n)