The solution you provided runs in O(n) time and can be brought down to O(1) ( which is not much interesting since it is just a closed formula), but the O(log N) is an interesting approach, take a look at it.
I am referring to the calculation of nth fibonacci number
The fibonacci solution is not O(n) because there's no computer that's going to be able to compute operations resulting in a 711 bit number if given a value of 1024 (which has input size 10 in binary).
So it's more correct to say pseudo polynomial.
Even with the "O(1)" approximation formula it won't work in practice because of the huge number of bits these numbers require.
The numbers produced are exponential. And exponential is going to have some serious consequences in practice.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
The solution you provided runs in
O(n)
time and can be brought down toO(1)
( which is not much interesting since it is just a closed formula), but theO(log N)
is an interesting approach, take a look at it.I am referring to the calculation of nth fibonacci number
The fibonacci solution is not O(n) because there's no computer that's going to be able to compute operations resulting in a 711 bit number if given a value of 1024 (which has input size 10 in binary).
So it's more correct to say pseudo polynomial.
Even with the "O(1)" approximation formula it won't work in practice because of the huge number of bits these numbers require.
The numbers produced are exponential. And exponential is going to have some serious consequences in practice.