Еще один алгоритм вычисления чисел Фибоначчи

Я разве писал, что собираюсь перемножать длинные числа за O(n)?

Еще один алгоритм вычисления чисел Фибоначчи

Вы фиксируете максимальную длину строки. Т.е. превращаете ее в константу. Разве в этом случае не выполняется равенство O(k*N*log(N)) = k*O(N*log(N))?

Еще один алгоритм вычисления чисел Фибоначчи

Так-то статью я написал вчера вечером, а тот коммент написан сегодня утром.

Еще один алгоритм вычисления чисел Фибоначчи

Если так рассуждать, то асимптотика алгоритма быстрой сортировки применительно к строкам произвольной длины (и даже числам произвольной величины) тоже не N * log(N).

Еще один алгоритм вычисления чисел Фибоначчи

Честно говоря я сам только сейчас заметил :) Возможно, где-то в подсознании рекурсивная функция вычисления F(N) ассоциируется с факториалом.

Еще один алгоритм вычисления чисел Фибоначчи

Да, он там был упомянут, но там нет объяснения алгоритма. O(log N) относится к количеству арифметических операций