Fibonacci numbers complex Time complexity

Published: at 05:30 AM

What is Fibonacci?

The Fibonacci sequence is a famous series of numbers where each number is the sum of the two preceding numbers. Starting from 0 and 1, the sequence continues as 1, 2, 3, 5, 8, 13, 21, 34, and so on. It’s named after Leonardo Fibonacci, an Italian mathematician from the 13th century who introduced it while studying rabbit populations.

Properties and Applications:

The Fibonacci sequence exhibits fascinating mathematical properties and has real-world applications in various fields, including:

Generating Fibonacci Numbers:

Here are two common ways to generate Fibonacci numbers:

1. Recursive Approach:

function fibonacciRecursive(n) {
  // Base case
  if (n < 2) {
    return n;
  }

  // Recursive case
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// Example usage
const recursiveResult = fibonacciRecursive(10);
console.log("Recursive result:", recursiveResult);

This method defines a function fibonacci that takes a number n and recursively calls itself to calculate the nth Fibonacci number. It can be computationally expensive for larger values of n.

2. Iterative Approach:

function fibonacciIterative(n) {
  // Initialize variables
  let a = 0;
  let b = 1;

  // Iterate up to the desired number
  for (let i = 0; i < n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }

  return a;
}

// Example usage
const iterativeResult = fibonacciIterative(10);
console.log("Iterative result:", iterativeResult);

This approach uses two variables to store the previous two Fibonacci numbers and iteratively updates them to compute the next one. It’s more efficient for bigger n.

Two different ways to calculate the Fibonacci sequence in JavaScript:

Recursive Approach:

function fibonacci(num) {
  if (num <= 1) {
    return 1;
  }

  return fibonacci(num - 1) + fibonacci(num - 2);
}

This function uses recursion to calculate the nth Fibonacci number. Here’s how it works:

  1. Base Case: If num is less than or equal to 1, it returns 1 because the first two numbers in the sequence are 1 and 1.
  2. Recursive Case: Otherwise, it calls itself twice with num - 1 and num - 2 as arguments. These represent the previous two Fibonacci numbers needed to calculate the current one.
  3. The returned values from the recursive calls are added and returned as the numth Fibonacci number.

Iterative Approach:

function fibonacci(num) {
  var a = 1,
    b = 0,
    temp;

  while (num >= 0) {
    temp = a;
    a = a + b;
    b = temp;
    num--;
  }

  return b;
}

This function uses an iterative approach to calculate the numth Fibonacci number. Here’s how it works:

  1. It initializes two variables a and b with the first two Fibonacci numbers (1 and 0).
  2. It uses a while loop that iterates as long as num is non-negative.
  3. Inside the loop, it performs the following:
    • It stores the current value of a in a temporary variable temp.
    • It updates a with the sum of a and b.
    • It updates b with the previous value of a stored in temp.
    • It decrements num by 1, effectively counting down the number of iterations needed.
  4. After the loop completes, b holds the numth Fibonacci number, which is returned.

Key Differences:

Both approaches ultimately produce the same result, though the iterative approach is generally preferred for better performance with larger numbers.

💁‍♀️ take a note that while loop more faster than recursive.

Big O notation

In a nutshell, Big O notation is a way to express the growth rate of an algorithm’s execution time (or space complexity) in relation to the size of its input. It helps us compare and analyze the efficiency of different algorithms without getting bogged down in specific implementation details.

AlgorithmTime ComplexitySpace Complexity
RecursiveO(2^n)O(n)
IterativeO(n)O(1)

Recap

Beyond the Basics:

Summary: