It's not. Multiplication can't in general be done in constant time (and the exponentiation algorithm is inefficient as well). You might argue that we're working with ints here, so yes it can, but in that case all of these are constant time.
It depends on what you consider an operation, doesn't it? You can consider multiplication to be an operation, or you can count more basic operations, such as MOVs and SUMs. I think for Fibonacci, number of additions is a good measure of complexity.
It depends on what you consider an operation, doesn't it?
Exactly. I see far too many people lately who want to point out the technically correct (a.k.a. best kind of correct) version of algorithmic complexity where e.g. multiplication is not constant time. Often this is paired with the contrasting complexity analyses having different meanings for the N in the big O notation, e.g. bit complexity of input vs. number of elements input. Note, this is not the case above, but is often what I see happen. It's very sloppy to directly compare the two as they are making wildly different assumptions on what is constant time. The model matters. An example used in a parallel computing class I took was that comparison based sorting on P parallel processors could be done in log N time (less than the Nlog(N) lower bound of comparison based sorting) in the PRAM model where memory access across parallel processors is still O(1).
Comments
Why do they all(except Hackaton) use an exponential complexity algorithm for a polynomial time problem? Linear, even.
The math phd one is constant time :)
It's not. Multiplication can't in general be done in constant time (and the exponentiation algorithm is inefficient as well). You might argue that we're working with ints here, so yes it can, but in that case all of these are constant time.
It depends on what you consider an operation, doesn't it? You can consider multiplication to be an operation, or you can count more basic operations, such as MOVs and SUMs. I think for Fibonacci, number of additions is a good measure of complexity.
Exactly. I see far too many people lately who want to point out the technically correct (a.k.a. best kind of correct) version of algorithmic complexity where e.g. multiplication is not constant time. Often this is paired with the contrasting complexity analyses having different meanings for the N in the big O notation, e.g. bit complexity of input vs. number of elements input. Note, this is not the case above, but is often what I see happen. It's very sloppy to directly compare the two as they are making wildly different assumptions on what is constant time. The model matters. An example used in a parallel computing class I took was that comparison based sorting on P parallel processors could be done in log N time (less than the Nlog(N) lower bound of comparison based sorting) in the PRAM model where memory access across parallel processors is still O(1).
The exponentiate function is in linear time, so it's O(n).
Too bad, it could be O(log n)...