What is the best way to find the k closest points to the origin out of a list of n points?
input.sorted()[0..<k]
O(N Log(N))
Run the test sort program. It times the sort and then divides the time by n*Log(n) the result is roughly constant
- take the first k items.
- find the highest.
- check the remaining items against the highest.
- if it's higher drop the highest, find the new highest, repeat.
O(N) Each item gets checked once. Score!
O(NK)
if K is small it's lost in the noise.
Somewhere in the neighborhood of Log(n)
Bad things, or well slow things, O(N^2) things.