News for hackers. Stuff that matters.
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.