It depends on problems and it is not always a simple yes or no. For the Fibonacci numbers, if you want exact results instead of floating point approximations, we need to use big integers for n roughly bigger than 100 on 64-bit machines. For 32 bit machines the bound is less than 50. If you restrict yourself in this range, you may just use something simpler than algorithm with the best time complexity under a O(1) arithmetic assumption.