Fibonacci numbers

Q: What is the time complexity of finding the Nth fibonacci term by recursion?

The time complexity by recursion is O(2N).

Q: What is the time complexity of finding Nth fibonacci term with DP?

For finding the Nth fibonacci number, we got O(N) time complexity in the dynamic programming method.

Introduction

The fibonacci series is the number sequence in which the given number results from adding the two previous numbers. The terms in the Fibonacci sequence are as follows:

The individual numbers in this sequence are called Fibonacci numbers. The Fibonacci sequence is a fantastic mathematical concept found in various places, including seashell patterns and the Parthenon.

Properties of Fibonacci Numbers

The ADDITION Rule

F_{N + K} = F_K . F_{N + 1} + F_{K - 1} . F_N

Applying Addition Rule to the case, K = N

F_{N + N} = F_N . F_{N + 1} + F_{N - 1} . F_N

F_2N = F_N ( F_{N + 1} + F_{N - 1})

From the above property, we can prove that for any positive integer K, F_NK is the multiple of F_N(By the Induction Hypothesis).
The inverse of the above property is true since, if F_M is multiple of F_N, then M is also the multiple of N.
Cassini’s Identity

F_{N - 1} . F_{N + 1} - F_N² = (-1)^N

This identity was given by Giovanni Domenico Cassini, an Italian mathematician. In the mathematical expression, N is the variable and it can have values from 1…..N.

For eg., if ‘N’ is an odd number, i.e. 1, 3, 5,... then (-1)^N+1 = +1 in every case. But if we take even value here, we will get the result as -1.

GCD Identity

For M, N >= 1

GCD(F_M , F_N) = F_{GCD (M, N)}, where M, N are integers

The Golden Ratio Approach

The golden ratio is defined as the limit of the ratio of successive terms in the Fibonacci sequence.

Now, if we divide F₂with F₁, we get,

F₂ / F₁ = 1 / 1 = 1

F₃ / F₂ = 2 / 1 = 2

F₄ / F₃ = 3 / 2 = 1.5

F₅ / F₄ = 5 / 3 = 1.667

F₆ / F₅ = 8 / 5 = 1.6

F₇ / F₆ = 13 / 8 = 1.625

F₈ / F₇ = 21 / 13 = 1.61538

F₉ / F₈ = 34 / 21 = 1.619047

F₁₀ / F₉ = 55 / 34 = 1.61765

F₁₁ / F₁₀ = 89 / 55 = 1.61818

F₁₂ / F₁₁ = 144 / 89 = 1.617975

F₁₃ / F₁₂ = 233 / 144 = 1.61805

and so on.

The golden ratio is coming about 1.618, as it means that as ‘N’ becomes sufficiently large, the fibonacci sequence approaches or approximates a geometric sequence. So, starting at number 144, and if we multiply 144 by 1.618, we get 233 (Approx.), the next element in the sequence. If we now multiply 233 with 1.618, we get approximately 377. Hence this golden ratio helps to approximate the next number in the series easily.

The formula for golden ratio is,

(1 + √5)^N - (1 - √5)^N

F_N = ------------------------------

2^N . √5

For example, let us find out the 8^th element in the sequence using the formula,

(1 + √5)⁸ - (1 - √5)⁸

F₈ = ------------------------------ = 21

2⁸ . √5

Code:

// To print the Nth Fibonacci Number.
#include <bits/stdc++.h>
using namespace std;

// The approx value of the golden ratio approach
double goldenRatio = 1.6180339;

// Taking an array of size, 'N' = 5
int fibonacciSeries[5] = {0, 1, 1, 2, 3};

// The function to find Nth fibonacci number
int fibonacci(int N){

  // The fibonacci no.s for N < 5
  if(N < 5)
  return fibonacciSeries[N];

  // Or else to start counting from the 4th term
  int i = 4, func = 4;
  while(i < N){
func = round(func * goldenRatio);
i++;
}
  return func;
}

// Main program
int main(){
  int N = 10;
  cout << N << "th Fibonacci number in the series: " << fibonacci(N)
<< endl;
  return 0;
}

Output:

10th Fibonacci number in the series: 68

The matrix multiplication in O(log N)

Code of Fibonacci Number Matrix Multiplication in C++

// To find the Nth Fibonacci Number in O(log N) time complexity

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 2;
const int mod = 1e9 + 7;

// Function to multiply two square matrices
vector<vector<int> > multiply(vector<vector<int>> &A, vector<vector<int> > &B){
  int t = A.size();
  vector<vector<int> > ans(t, vector<int>(t, 0));
  for(int i = 0; i < t; i++){
  for(int j = 0; j < t; j++){
  for(int k = 0; k < t; k++){
ans[i][j] += A[i][k] * B[k][j];
}
}
}
  return ans;
}

// Function for matrix exponentiation
vector<vector<int> > matrixMultiplication(vector<vector<int> > &V, int N){
  if(N == 0){
  int t = V.size();
  vector<vector<int> > ans(t, vector<int>(t, 0));
  for(int i = 0; i < t; i++){
ans[i][i] = 1;
}
  return ans;
}
  if(N == 1){
  return V;
}
  vector<vector<int> > temp = matrixMultiplication(V, N/2);
  vector<vector<int> > ans = multiply(temp, temp);
  if(N & 1){
ans = multiply(ans, V);
}
  return ans;
}

signed main(){
  int N;
  cout << "Enter the Nth position to find the matrix exponentiation:

    ";
  cin >> N;
  vector<vector<int> > V(2, vector<int>(2, 0));
V[0][0] = V[0][1] = V[1][0] = 1;
V[1][1] = 0;
  vector<vector<int> > ans = matrixMultiplication(V, N);
  int t = ans.size();
  for(int i = 0; i < t; i++){
  for(int j = 0; j < t; j++){
  cout << ans[i][j] << " ";
}
  cout << endl;
}
}

Input:

Enter the Nth position to find the matrix exponentiation: 7

Output:

21 13
13 8

Time Complexity

The time complexity depends on two factors:

Matrix multiplication, K³

As the matrix moves ‘column by column’ or ‘row by row’, we will get a matrix K x K where ‘K’ represents the number of states. We can notice that in our code, the function ‘multiply’ has three nested for loops which takes time complexity = K x K x K = K³.

Log(N)

For computing the large input, we raise the matrix to the power N, which takes log(N) time.

Hence, multiplying both the factors (1) and (2), we get => K³. log(N)

Therefore, the time complexity will be O(K³ log N).

Space Complexity

The space complexity is O(log N) since we raise the matrix to the Nth power. Hence it will take O(log N) additional space.

Frequently Asked Questions

What is the golden ratio in the Fibonacci sequence?

From atoms to the massive stars in the sky has patterns. The golden ratio reveals predictable or observable patterns. This ratio is derived from the Fibonacci sequence, named after Leonardo Fibonacci, an Italian mathematician.

What is the time complexity of finding the Nth fibonacci term by recursion?

The time complexity by recursion is O(2^N).

What is the time complexity of finding N^th fibonacci term with DP?

For finding the N^th fibonacci number, we got O(N) time complexity in the dynamic programming method.

Here, we store the previous terms, which are overlapping to reduce the time complexity.

Key Takeaways

In this blog, we learned about Fibonacci numbers, their properties, the working of matrix multiplication in O(log N) time complexity, and the golden ratio approach.

Try problems related to the Fibonacci numbers here on CodeStudio to understand the working concept of Fibonacci numbers. To be more confident in data structures and algorithms, try out our DS and Algo Course.