Re:Sleeping Through the Technical Interview (2022)
by ctenb on Saturday July 08, 2023 @06:03AM
(#36642960)
Can the wall time be considered constant if it depends on the magnitude of the numbers to sort? A list of numbers between 1 and 1000 will be much faster to sort than a list of numbers between 1 and 10^100. EDIT: I did get the joke when I read your post, and laughed to myself, so well done :)
[ Parent
| on HN ]
Re:Sleeping Through the Technical Interview (2022)
by xena on Saturday July 08, 2023 @06:05AM
(#36642971)
The constant is the biggest number in the list multiplied by the sleep multiplicand. That plus overhead gets you the approximate runtime of the function.
Re:Sleeping Through the Technical Interview (2022)
by ctenb on Sunday July 09, 2023 @03:21PM
(#36657932)
Yeah, but technically that doesn't qualify as a constant since it depends on the input. If you explicitly constrain the problem space such that the magnitude of the numbers in the list is bounded by a fixed upper bound, then it works out. That's fine though, but then it's not a fully general sorting algorithm, like e.g quicksort
Re:Sleeping Through the Technical Interview (2022)
by Tainnor on Sunday July 09, 2023 @09:19PM
(#36660897)
If you just repeat the same number a million times, then the threads will all be scheduled to run at the same time, but of course, your computer doesn't have a million cores, so the threads will have to be executed partially in sequence. That means, even if you assume the largest integer is a constant (valid for some integer types, but notably not Integer in Haskell), the runtime will be proportional to the number of elements in the list.