Just to be explicit: You are \$O(n)\$ in time and \$O(n)\$ in memory. I don't believe you can do better in integer arithmetic (when actually calculating it) in time, but memory could be \$O(1)\$.

As has been pointed out by Peter Cordes, there is a "Closed form" for the Fibonacci sequence, which means that if you have a constant time infinite precision floating point system, you can achieve \$O(1)\$. Computer floating point can achieve an approximation, but I think you will get more accurate results with integer math.

If you use your function iteratively to print the Fibonacci sequence, your time result would be \$O(n^2)\$, and that can be done in \$O(n)\$.

Just to be explicit: You are \$O(n)\$ in time and \$O(n)\$ in memory. I don't believe you can easily do better in integer arithmetic (when actually calculating it) in time, but memory could be \$O(1)\$.

As has been pointed out by Peter Cordes, there is a "Closed form" for the Fibonacci sequence, which means that if you have a constant time infinite precision floating point system, you can achieve \$O(1)\$. Computer floating point can achieve an approximation, but I think you will get more accurate results with integer math.

As also pointed out by Peter Cordes, there is a "Lucas sequence method" that can do \$O(\log{n})\$ given integer multiplication and a fair bit more complexity.

If you use your function iteratively to print the Fibonacci sequence, your time result would be \$O(n^2)\$, and that can be done in \$O(n)\$.

Just to be explicit: You are \$O(n)\$ in time and \$O(n)\$ in memory. I don't believe you can do better (when actually calculating it) in time, but memory could be \$O(1)\$.

If you use your function iteratively to print the Fibonacci sequence, your time result would be \$O(n^2)\$, and that can be done in \$O(n)\$.

Just to be explicit: You are \$O(n)\$ in time and \$O(n)\$ in memory. I don't believe you can do better in integer arithmetic (when actually calculating it) in time, but memory could be \$O(1)\$.

As has been pointed out by Peter Cordes, there is a "Closed form" for the Fibonacci sequence, which means that if you have a constant time infinite precision floating point system, you can achieve \$O(1)\$. Computer floating point can achieve an approximation, but I think you will get more accurate results with integer math.

If you use your function iteratively to print the Fibonacci sequence, your time result would be \$O(n^2)\$, and that can be done in \$O(n)\$.