# Fibonacci numbers

Writing a method that calculates a particular Fibonacci number is still a frequently used programming exercise during interviews. During interviews, the test is of simple programming ability, but there are a variety of ways to solve this problem ranging from exponential to sub-linear with respect to the number in the sequence desired.

#### Typical solutions: Exponential to Linear

The typical solution to this problem given is one of two options: either recursively solving in exponential time (O(2^n)) or linear (O(n)) where “n” is the number in the sequence. The recursive solution can further be optimized to O(n) running time with an addition of O(n) extra storage by using memoization. In the implementations below note the use of java.util.BigInteger since Fibonacci numbers can overflow **ints** and **longs** very quickly. These 3 versions of fibonacci are implemented below in Java:

#### More advanced and efficient solutions

Fibonacci numbers can actually be found much faster than linear. There exists a logarithmic solution just as capable as the algorithms above, and there even exists a constant time solution that works but is extremely limited by precision. Here is the code for both the logarithmic solution in Java:

The logarithmic algorithm was implemented using Dijkstra’s algorithm. There also exists a constant time O(1) function that calculates Fibonacci numbers by relying on the fact that the ratio of F(n+1)/F(n) converges to the golden ratio as n approaches infinity. Binet’s formula for calculating fibonacci numbers.