News for hackers. Stuff that matters.

A comment on Complexity Theory’s 50-Year Journey to the Limits of Knowledge. Parent comment

Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by lacker on Saturday August 19, 2023 @02:59AM (#37186271)
I guess even if you allow probabilistic algorithms and expected runtime, you still can't have an algorithm that runs faster as the input size grows. Because... it takes O(log n) time to calculate any random variable whose expected value has a denominator of size n? I'm not entirely sure but that seems right to me.
[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by Dylan16807 on Saturday August 19, 2023 @03:15AM (#37186349)
That's for randomly sampling a large input?

If each piece of input is already independent, then you don't have to calculate that, you can just use the input in order.

[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by daveFNbuck on Saturday August 19, 2023 @11:06AM (#37189522)
With probabilistic algorithms, you still have the fundamental limitation that there's a lower-bound to how fast an algorithm can run. You can't keep getting faster indefinitely.
[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by lacker on Tuesday August 29, 2023 @02:44PM (#37312083)
You could get faster in expected value. What if the time on input of length n was an expected value of 100 + 1/n?

That isn't possible, but it might not quite be obvious why that isn't possible.

[ Parent | on HN ]
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by daveFNbuck on Tuesday August 29, 2023 @08:23PM (#37316029)
Having a constant runtime means there's a constant bound on the runtime, not that the runtime is an exact constant value. 100 + 1/n would still be constant, as it's bounded above and below by constants.

To have sub-constant time it would have to go to 0 as n increases, as otherwise we could bound the time below by a constant. This isn't possible, as a computer will take at least 1 time unit on every input. So the expected time will always be at least 1.

[ Parent | on HN ]