Calculating Fibonnacci Numbers
In this lesson, we'll look at the classic method to find the nth Fibonacci number and its time complexity using recurrence relations
Classic Recursive Implementation of The Fibonacci Series
Before we dive into what dynamic programming is, let’s have a look at a classic programming problem Fibonacci Series. You have probably already seen it, but let’s start with a quick refresher. The Fibonacci series is a series of numbers in which each number is the sum of the preceding two numbers. The first two numbers are 0 and 1. So it looks like:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Here is a C++ function that returns nth the Fibonacci number.
#include <iostream>using namespace std;int fib(int i){if (i <= 1)return i;return fib(i - 1) + fib(i - 2);}int main(){int n = 6;cout << fib(n) << endl;}
Time Complexity with Recurrence Relations
To calculate the time complexity of the code, we can solve a recurrence relation,
...
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy