2 ms·
Intuitively i feel like it makes sense though. The k in O(n^k) roughly corresponds with how many times you loop through the data. Its really hard to imagine a u
by bawolff 5y ago
Intuitively i feel like it makes sense though. The k in O(n^k) roughly corresponds with how many times you loop through the data. Its really hard to imagine a useful algorithm where you need to loop through the data exactly 153 times but then stop there. Either you're going to need to grow the number of loops with input size (be exponential) or surely you got all the data you needed the first 14 times you went through the data.
I guess that's not really very rigorus it just feels intuitively right. I just can't imagine a system where you always gain new information regardless of input size on loop iteration 561, but never on iteration 562.
Its somewhat similar to how in pure math problems where it seems kind of suspicious if the answer is something like exactly 8.3781 and the problem statement didn't have any related constants in it. Integers are expected, Irrational numbers are expected, decimals with exactly 4 digits sound suspicious.