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 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.