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