Time Complexity of Fibonacci Series

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding numbers, starting from 0 and 1.  

The sequence goes like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144………………….

Each number in the Fibonacci series is called a Fibonacci number. The sequence was first described in Europe by Leonardo of Pisa, an Italian mathematician also known as Fibonacci, in his book "Liber Abaci" published in 1202.

The Fibonacci series has numerous applications in mathematics, science, and computer science. For example, it appears in patterns found in nature, such as the arrangement of leaves on a stem or the spiral patterns in shells and sunflowers. In computer science, the Fibonacci series is commonly used as an example of recursive programming and is used in algorithms such as dynamic programming and memorization.

Time Complexity

The time complexity of generating the Fibonacci series can be analyzed using Big O notation. The simplest way to generate the Fibonacci series is through a recursive function that calls itself twice for each number except the first two. This function has a time complexity of O(2^n), where n is the number of Fibonacci numbers to be generated. This is because each recursive call creates two more recursive calls, resulting in an exponential increase in the number of function calls as n increases.

However, we can improve the time complexity by using dynamic programming techniques. We can store the previously calculated Fibonacci numbers in an array and reuse them to calculate the subsequent numbers. This reduces the number of function calls and results in a time complexity of O(n), which is a significant improvement over the recursive solution.

Additionally, there is a closed-form expression for the Fibonacci series, which involves using the golden ratio. This solution has a time complexity of O(1), as it involves only simple arithmetic operations.

In summary, the time complexity of generating the Fibonacci series can range from O(2^n) for a naive recursive solution to O(n) for a dynamic programming solution, and even O(1) for the closed-form expression.

Here is an example of how to generate the Fibonacci series in Python:

Using a recursive function:

def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# print the first 10 Fibonacci numbers
for i in range(10):
print(fibonacci(i))

Output:

0
1
1
2
3
5
8
13
21
34

Using a loop and a list:

def fibonacci(n):
fib_list = [0, 1]
for i in range(2, n+1):
fib_list.append(fib_list[i-1] + fib_list[i-2])
return fib_list
# print the first 10 Fibonacci numbers
fib_series = fibonacci(10)
for fib_num in fib_series:
print(fib_num)

Output:

0
1
1
2
3
5
8
13
21
34

Fibonacci series in Python using a recursive function without optimizing time complexity:

def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# print the first 10 Fibonacci numbers
for i in range(10):
print(fibonacci(i))
Fibonacci series using a loop and a list to optimize time complexity:
def fibonacci(n):
fib_list = [0, 1]
for i in range(2, n+1):
fib_list.append(fib_list[i-1] + fib_list[i-2])
return fib_list
# print the first 10 Fibonacci numbers
fib_series = fibonacci(10)
for fib_num in fib_series:
print(fib_num)

Here is an example of how to generate the Fibonacci series in C:

Using a loop:

#include <stdio.h>
int main() {
int n, i, fib, prev1 = 0, prev2 = 1;
printf("Enter the number of Fibonacci numbers to generate: ");
scanf("%d", &n);
printf("The first %d Fibonacci numbers are:\n", n);
for (i = 0; i< n; i++) {
if (i<= 1) {
fib = i;
        } else {
fib = prev1 + prev2;
            prev1 = prev2;
            prev2 = fib;
        }
printf("%d ", fib);
    }
printf("\n");
return 0;
}

Using a recursive function:

#include <stdio.h>
int fibonacci(int n) {
if (n == 0) {
return 0;
    } else if (n == 1) {
return 1;
    } else {
return fibonacci(n-1) + fibonacci(n-2);
    }
}
int main() {
int n, i;
printf("Enter the number of Fibonacci numbers to generate: ");
scanf("%d", &n);
printf("The first %d Fibonacci numbers are:\n", n);
for (i = 0; i< n; i++) {
printf("%d ", fibonacci(i));
    }
printf("\n");
return 0;
}

For example, if the user enters 10, the output will be:

The first 10 Fibonacci numbers are:
0 1 1 2 3 5 8 13 21 34

Fibonacci series using a loop without optimizing time complexity:

#include <stdio.h>
int main() {
int n, i, fib, prev1 = 0, prev2 = 1;
printf("Enter the number of Fibonacci numbers to generate: ");
scanf("%d", &n);


printf("The first %d Fibonacci numbers are:\n", n);
for (i = 0; i< n; i++) {
if (i<= 1) {
fib = i;
        } else {
fib = prev1 + prev2;
            prev1 = prev2;
            prev2 = fib;
        }
printf("%d ", fib);
    }
printf("\n");
return 0;
}

Fibonacci series using a loop and optimizing time complexity:

#include <stdio.h>
int main() {
int n, i;
unsigned long long fib, prev1 = 0, prev2 = 1;
printf("Enter the number of Fibonacci numbers to generate: ");
scanf("%d", &n);
printf("The first %d Fibonacci numbers are:\n", n);
for (i = 0; i< n; i++) {
if (i<= 1) {
fib = i;
        } else {
fib = prev1 + prev2;
            prev1 = prev2;
            prev2 = fib;
        }
printf("%llu ", fib);
    }
printf("\n");
return 0;
}