News for hackers. Stuff that matters.
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by quickthrower2 on Saturday August 19, 2023 @09:21PM (#37195076)
It should have been N+K not N-K
Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by daveFNbuck on Sunday August 20, 2023 @02:55AM (#37196843)
I'm not sure what your big-O expression is supposed to mean, but if a sequence is decreasing and bounded below (which runtime is) then it has a limit. Since the sequence is discrete, it can't get arbitrarily close to the limit without reaching it. So at some point the runtime will stop decreasing.

You can approximate the runtime with a function that decreases forever, but the actual runtime will be constant for large enough n.

Re:Complexity Theory’s 50-Year Journey to the Limits of Know... by quickthrower2 on Sunday August 20, 2023 @03:39AM (#37197010)
It is for a typical case not a specific case. The mean time, if you like.