Algorithms for Coding Interviews in Python/

...

/

Calculating Fibonacci Numbers

Calculating Fibonacci Numbers

In this lesson, we'll look at the classic method to find the nth Fibonacci number and its time complexity using recurrence relations.

We'll cover the following...

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, the 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 Python function that returns the nthn^{th} Fibonacci number.

This is the Fibonacci golden spiral. The width of each square represents a Fibonacci number.

def fib(num):
  """
  Finds nth fibonacci number
  :param num: An integer number
  :return: nth fibonacci number
  """
  if num <= 1:
    return num
  return fib(num - 1) + fib(num - 2)
# Driver code to test above function
if __name__ == '__main__':
  num = 6
  print(fib(6))

Time complexity with recurrence relations

To calculate the time complexity of the code, we can solve a recurrence relation,

{T(0)=0, ...

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy