9 Fibonacci Algorithms: The Most Complete Solutions
By Long Luo
The [1] are the numbers in the following integer sequence:
We can see the fibonacci series seqences in the natrual world like the sunflower, the nautilus and the galaxy.
In mathematical terms, the sequence of Fibonacci numbers is defined by the recurrence relation
with seed values and .
The Fibonacci sequence is often used in introductory computer science courses to explain recurrence relations, dynamic programming, and proofs by induction. Because the Fibonacci sequence is central to several core computer science concepts, the following programming problem has become fairly popular in software engineering interviews.
Given an input , return the number in the Fibonacci sequence.
Below I’ve listed approaches to this problem. These different solutions illustrate different programming and algorithmic techniques that can be used to solve other problems. You’ll notice that many of these solutions build from previous solutions.
Solution 1 Lookup Table - 32 bit signed integers only
If we don’t need to solve very large values and are time-sensitive, we can calculate all values in advance.
This function will work strictly in the case that we’re dealing with bit signed integers (which could be a constraint in languages like Java, C/C++, etc.)
The Fibonacci sequence grows very quickly. So fast, that only the first Fibonacci numbers fit within the range of a bit signed integer. This method requires only a quick list lookup to find the nth Fibonacci number, so it runs in constant time. Since the list is of fixed length, this method runs in constant space as well.
1 | class Solution { |
Analysis
- Time Complexity:
- Space Complexity:
Solution 2 Recursion
A simple method that is a direct recursive implementation mathematical recurrence relation is given above.
1 | //Fibonacci Series using Recursion |
Analysis
- Time Complexity: , where is the golden ratio ().
If we count the number of calls that this algorithm makes for any n, we will find its runtime complexity.
Let refer to the number of calls to fib1 that are required to evaluate fib1(n).
When fib1(0) or fib1(1) is called, fib1 doesn’t make any additional recursive calls, so and must equal 1.
For any other n, when fib1(n) is called, fib1(n - 1) and fib1(n - 2) are also called.
So
Using more advanced mathematical techniques, like generating functions, one can solve the recurrence , and find that scales as .
If the original recursion tree were to be implemented then this would have been the tree but now for n times the recursion function is called.
Original tree for recursion:
1 | fib(5) |
Optimized tree for recursion for code above:
1 | fib(5) |
- Space Complexity: if we consider the function call stack size, otherwise .
Solution 3 Dynamic Programming
We can avoid the repeated work done in Recursion solution by storing the Fibonacci numbers calculated so far.
1 | // Dynamic Programming |
Analysis
- Time Complexity:
- Space Complexity:
Solution 4 DP using memoization(Top down approach)
We can avoid the repeated work done in Solution 2 Recursion by storing the Fibonacci numbers calculated so far. We just need to store all the values in an array.
1 | // Initialize array of dp |
Analysis
- Time Complexity:
- Space Complexity:
Solution 5 Iterative (Space Optimized Method 3)
We can optimize the space used in Solution 3 Dynamic Programming by storing the previous two numbers only because that is all we need to get the next Fibonacci number in series.
This solution is one of the simplest and most efficient algorithms on this list. This function has a loop that runs through n iterations before returning, and each iteration does constant work, making the algorithm run in time. This function doesn’t use any extra data structures, and it isn’t recursive, so we can say that it uses space.
1 | // Fibonacci Series using Space Optimized Method |
Analysis
- Time Complexity:
- Space Complexity:
Solution 6 Recurrence Matrix
This is the most mathematical solution, and it requires some basic understanding of matrix multiplication.
Consider the following matrix :
If and are the th and the th Fibonacci numbers, the following matrix product can give us the ith Fibonacci number :
Using this property of , one can find by computing the product
and returning the first element of the vector.
1 | class Solution { |
Analysis
- Time Complexity:
- Space Complexity:
Solution 7 Fast Matrix Power(Optimized Method 6)
The Solution 6 Recurrence Matrix can be optimized to work in time complexity. We can do recursive multiplication to get in the previous method (Similar to the optimization done in this post).
The key here is to compute using the successive square method. Using this algorithm, is computed in time(Note that for a fixed matrix size, the matrix muliplication algorithm takes a constant amount of time).
Then, is multiplied by , and the top elemen of the product is returned.
This algorithm uses to compute , and constant space, as the intermediary matricies can be reclaimed by the garbage collecter.
1 | class Solution { |
Analysis
- Time Complexity: .
- Space Complexity: , if we consider the function call stack size, otherwise .
Solution 8 O(logn) Time
Below is one more interesting recurrence formula that can be used to find nth Fibonacci number in time.
If is even then :
If is odd then
How does this formula work?
The formula can be derived from above matrix equation.
Taking determinant on both sides, we get:
Moreover, since for any square matrix , the following identities can be derived (they are obtained form two different coefficients of the matrix product)
By putting in equation (8.1),
Putting in equation(8.1).
Putting in equation(8.2)
By putting:
To get the formula to be proved, we simply need to do the following
If is even, we can put
If is odd, we can put
Below is the implementation of above idea.
1 | public static int MAX = 1000; |
Analysis
- Time Complexity: as we divide the problem to half in every recursive call.
- Space Complexity:
Solution 9 Math Formula
We first look at the equation:
To solve (9.1) for the Fibonacci numbers, we first look at the equation
This equation is called a second-order, linear, homogeneous difference equation with constant coefficients, and its method of solution closely follows that of the analogous differential equation.
Our idea is to guess the general form of a solution, find two such solutions, and then multiply these solutions by unknown constants and add them. This results in a general solution to (9.2), and one can then solve by satisfying the specified initial values.
To begin, we guess the form of the solution as
where is an unknown constant.
Substitution of this guess into the equation, results in:
or upon division by and rearrangement of terms,
Use of the quadratic formula yields two roots, both of which are already familiar. We have:
We have thus found two independent solutions to (9.2) of the form (9.3), and we can now use these two solutions to find a solution to (9.1). Multiplying the solutions by constants and adding them, we obatin:
which must satisfy the initial values ,.
Application of the values for and results in the system of equations given by
we can solve for and to obtain:
,.
then derives the surprising formula:
known as Binet’s formula.
In this method we directly implement the formula for nth term in the fibonacci series.
1 | class Solution { |
Analysis
- Time Complexity: , this is because calculating takes time
- Space Complexity: .
References
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗