Home » Python » Python programs

# Python | Program to calculate n-th term of a Fibonacci Series

Here, we are going to learn **how to calculate the n-th term of a Fibonacci series using python program?**

Submitted by Sanjeev, on March 30, 2019

**Python program to calculate n-th term of Fibonacci series** with the help to two approaches (there are many approaches to calculate n-th term).

**Description:**

**First Approach: Dynamic Programming**

In this approach, we calculate all the terms of Fibonacci series up to n and if we need to calculate any other term which is smaller than n, then we don’t have to calculate it again.**Second Approach: By Formula**

In this approach we calculate the n-th term of Fibonacci series with the help of a formula.

Formula:phi = ( 1 + sqrt(5) ) / 2 A_{n}= phi^{n}/ sqrt(5)

**Example:**

Input: for n = 5 for n = 8 Output: a_{5}= 5 a_{8}= 21

**Procedure: Dynamic Programming Approach**

L[0] = 0, L[1] = 1 For loop from 2 to n+1 L[i] = L[i-1] + L[i -2] End of for

As you may observe that we are also storing each calculated value, so we can also use them later if necessary.

This is the benefit of Dynamic Programming over Recursion.

## Python code to calculate n-th term of a Fibonacci series

def dynamic_fibonacci(n): ''' This function will calculate fobonacci series with the help of dynamic programming. ''' l = [0]*(n+1) l[0] = 0 l[1] = 1 for i in range(2, n+1): l[i] = l[i-1] + l[i-2] return l # Time complexity O(n) def fibonacci_by_formula(n): ''' This function will calculate n-th term of fibonacci series with the help of a formula. ''' from math import sqrt phi = (1 + sqrt(5))/2 fib = round(pow(phi, n)/sqrt(5)) return fib # Time complexity O(1) def main(): n = 8 lst = dynamic_fibonacci(n) x = fibonacci_by_formula(n) print('By Dynamic Programming:',lst[n]) print() print('By Formula:',x) main()

**Output**

By Dynamic Programming: 21 By Formula: 21

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions