6 ms·
Nit: if number n is given in binary representation in the input, then an O(n)-algorithm runs in exponential time as n is an exponential function of log(n). Henc
by zschoche 3y ago
Nit: if number n is given in binary representation in the input, then an O(n)-algorithm runs in exponential time as n is an exponential function of log(n). Hence, log(n)^O(1)-time algorithms for the Fibonacci number are reasonable to exist, unless the decision version of the Fibonacci number is NP-hard.