5 ms·
In complexity theory, n is based on the length of the binary encoding of the input, NOT the decimal value as was used here. Therefore, the x-axis should be base
by dmg_83 17y ago
In complexity theory, n is based on the length of the binary encoding of the input, NOT the decimal value as was used here. Therefore, the x-axis should be based on n = log2(k), for each number k.
Overlooking this would lead one to believe there are known algorithms that solve NP-C problems in polynomial time (e.g., knapsack problem can be solved in polynomial time with respect to the decimal values of its inputs, but exponential with respect to the length of the binary encoding).
- sp332 17y ago(e.g., knapsack problem can be solved in polynomial time with respect to the decimal values of its inputs, but exponential with respect to the length of the binary encoding). That doesn't make any sense. The number of binary and decimal digits has a linear relation. I think the ratio is log(10) / log(2) or about 3.32 .
- mikhael 17y agoit does make sense; there are two issues here. one is that the author overlooked (or ignored) the fact that "input size" means number of bits. the number N uses ~log2(N) = M bits, so that is the input size, not N, and O(N) is O(2^M). the other is that addition of two D-digits numbers takes O(D) time (this is what the author means to expose in the article). as you have pointed out, the base (10, or 2, or anything else) does not matter for asymptotic analysis here, because the logarithm functions are all linearly related.
- sp332 17y agoAh, sorry I misread the contrasted "value vs. length". That does make sense.
- deleted 17y ago[deleted]
- pkrumins 17y agoYes, but you can also measure it by input value, like I did. It makes more sense to me to plot n vs. time(Fib(n)), because practically I'd want to know how "how fast" my algo runs if i give it n. What do you think about that?