3 ms·
Why do they all(except Hackaton) use an exponential complexity algorithm for a polynomial time problem? Linear, even.
by Fargren 13y ago
Why do they all(except Hackaton) use an exponential complexity algorithm for a polynomial time problem? Linear, even.
- marvy 13y agoThe math phd one is constant time :)
- wging 13y agoIt'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.
- Fargren 13y agoIt 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.
- dmunoz 13y ago> 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).
- deleted 13y ago[deleted]
- marcosdumay 13y agoThe exponentiate function is in linear time, so it's O(n). Too bad, it could be O(log n)...