Fibonacci Iterative vs. Recursive

Recursive approach:

Time Complexity:

fib(n):
if n <= 1
return 1
return fib(n - 1) + fib(n - 2)
T(n) = T(n-1) + T(n-2) + c
= 2T(n-2) + c //from the approximation T(n-1) ~ T(n-2)
= 2*(2T(n-4) + c) + c
= 4T(n-4) + 3c
= 8T(n-6) + 7c
= 2^k * T(n - 2k) + (2^k - 1)*c
Let's find the value of k for which: n - 2k = 0
k = n/2
T(n) = 2^(n/2) * T(0) + (2^(n/2) - 1)*c
= 2^(n/2) * (1 + c) - c
i.e. T(n) ~ 2^(n/2)
T(n) = T(n-1) + T(n-2) + c
= 2T(n-1) + c //from the approximation T(n-1) ~ T(n-2)
= 2*(2T(n-2) + c) + c
= 4T(n-2) + 3c
= 8T(n-3) + 7c
= 2^k * T(n - k) + (2^k - 1)*c
Let's find the value of k for which: n - k = 0
k = n
T(n) = 2^n * T(0) + (2^n - 1)*c
= 2^n * (1 + c) - c
i.e. T(n) ~ 2^n

Space Complexity:

Recursion tree for Fibonacci of 6

--

--

--

Re-learning the fundamentals of programming.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Salesforce Data Security

DRY — Don’t Repeat Yourself

Laptop

Dropped out of college to pursue programming

Sandesh Pandey (React Developer)

Short summary of Unit test, Widget test, Integration test in flutter.

Create a YAML Manifest Template in Monokle

Code Stories: An Introduction

How to get a last-minute tech internship (college and pre-college)

student working hard trying to get a last minute tech internship in software engineering or data science.

Feature Engineering Part -1 End of Tail Imputation.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Syed Tousif Ahmed

Syed Tousif Ahmed

Re-learning the fundamentals of programming.

More from Medium

Helix Search ~ Searching Algorithm

BackTracking(1) / Algorithm

Leetcode 1886. Determine Whether Matrix Can Be Obtained By Rotation

image.png

Backtracking Algorithm