Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by sp332 on Tuesday July 07, 2009 @01:01PM
(#691851)
(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 .
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by mikhael on Tuesday July 07, 2009 @01:22PM
(#691893)
it 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.
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by sp332 on Tuesday July 07, 2009 @02:51PM
(#692152)
Ah, sorry I misread the contrasted "value vs. length". That does make sense.
Re:On the Linear Time Algorithm For Finding Fibonacci Numbers
by pkrumins on Tuesday July 07, 2009 @05:37PM
(#692591)
Yes, 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?
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).