3 ms·
You can't have that because when N=K that's not a valid expression and when N>K you're putting a negative number in the big-O notation. You can't have negative
by daveFNbuck 3y ago
You can't have that because when N=K that's not a valid expression and when N>K you're putting a negative number in the big-O notation. You can't have negative runtime.
All algorithms have a lower-bound on runtime of 1. If a sequence is decreasing and bounded below, it converges to a value [1]. If the sequence is discrete, that means it reaches exactly that limit and never deviates from it.
[1] https://en.wikipedia.org/wiki/Monotone_convergence_theorem https://en.wikipedia.org/wiki/Monotone_convergence_theorem
- quickthrower2 3y agoIt should have been N+K not N-K
- daveFNbuck 3y agoI'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.
- quickthrower2 3y agoIt is for a typical case not a specific case. The mean time, if you like.