Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
davrosthedalek
on Dec 26, 2014
|
parent
|
context
|
favorite
| on:
Sleep sort (2011)
You can always scan through the array, rescale everything by 1/max(input). Then the sleep part is O(1) and the scan part is O(n) -> O(n) total.
JoshTriplett
on Dec 26, 2014
[–]
Division isn't O(1) for arbitrary values (potentially larger than a machine word).
pdw
on Dec 26, 2014
|
parent
|
next
[–]
The same is true for comparison though, isn't it?
dalke
on Dec 26, 2014
|
parent
|
prev
[–]
Sleep maxes out at 2147483647 = 2^31 seconds. Generally these problems assume the transdichotomous model, where the machine word size matches the problem size.
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
