Is an iterative solution for Fibonacci series pseudo-polynomial?

Question

So when we do an iterative solution to find the nth number in a Fibonacci sequence, we run a for loop (n-2) times. This would mean that the time complexity would be O(n). Is this correct or would it actually be pseudo-polynomial depending on the number of bits of the input, much like the Knapsack problem?

Answer 1

Here, I assume Fib(n) is an iterative version of a program that computes Fibonacci numbers. Perhaps something like:

def Fib(n):
    a, b = 0, 1
    for _ in xrange(n):
        a, b = b, a + b
    return a

"Fib(n) is pseudo-polynomial" means in this context that computing Fib is bounded by a polynomial of its argument, n, but isn't bounded by a polynomial function of the size of the argument, log(n). That's true in this case.

"Fib(n) is O(n)" is a statement about the running time of Fib with respect to the value of its argument. There's sometimes ambiguity what "n" is, but here there's none -- it's the input to Fib, otherwise "n" would refer to two different things in the original statement. That's true here (although see the technical side-note below).

"Fib is O(n)" is ambiguous. There are people who will tell you that n clearly refers to the argument, and there's others who will tell you that n always refers to the size of the argument. The truth is that it's ambiguous and if it's not clear in context you should say what you mean (or ask what it means if you hear it and are confused). One context where it's not ambiguous is when you're talking about classes of P/NP problems -- there it's assumed that complexities are always relative to the size of the input.

A technical side-note

The iterative version of Fib(n) performs O(n) arithmetic operations, but whether it's O(n) time depends on your computational model, and specifically whether it can perform arbitrary integer arithmetic operations in O(1) time. Personally, I'd be careful and say "Fib(n) performs O(n) arithmetic operations" rather than "Fib(n) is O(n)" -- and if you plot the running time of Fib(n), you'll find it's not linear time in practice, as real bignum implementations are certainly not O(1) for all basic operations.