509. Fibonacci Number

Prompt

You are asked to create a function that takes in an input of n and derive the fibonacci number when n is passed in. This is commonly denoted as F(n) where according to the constraints, n is an integer between 0 and 30 inclusive.

In case if you aren’t familiar with the Fibonacci Sequence, an example is as follows:

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

Starting from F(2), each number in the sequence is the sum of the 2 preceding ones starting. In other words, F(0) automatically equates to 0 and similarly, F(1) equates to 1. Deriving any fibonacci number from 2 or above, we would calculate the sum of the 2 preceding terms.

F(2) = F(2–1) + F(2–2)
F(2) = F(1) + F(0)
Because we know F(1) = 1 and F(0) = 0, we can replace those terms
F(2) = 1 + 0
F(2) = 1

Approach

This problem is testing your knowledge & understanding of the Fibonacci Sequence. If you know how it works in that every term starting from the 3rd (starting from F(2)) is calculated using the formula of deriving the sum of its 2 preceding terms, then you’re almost there!

Now the only thing left to decide on is whether you’ll write this code iteratively or recursively as you could write a solution for either or. From an asymptotic point of view, I believe this problem serves as a perfect case study to represent that though you can write the solution either recursively or iteratively, you should weigh both approaches and see what the potential tradeoffs are.

For instance, writing this solution recursively will utilize implicit call stack space, and if we draw out a decision tree or a tree diagram displaying the different decisions that can be made at each iteration, the total space-time complexity would be vastly different than if the code were to be implemented iteratively.

In short, the time complexity of the recursive code would be O(2^n) or exponential because in the worst case, if you calculate the number of nodes in the last level of the tree (or in other words, the leaf nodes), there would be 2^n of them in that level. According to the Power Series, the last level in a tree is going to be more than the sum of all of the nodes in its preceding levels combined so when we talk about asymptotic complexity, we can confidently say that our algorithm will be dominated by the leaf level nodes or 2^n nodes roughly in the worst case. Furthermore, the recursive implementation would use O(n) space because the number of levels in the tree wouldn’t surpass more than n levels when the call stack is at its tallest height.

Conversely, if we were to write this solution iteratively, the time complexity would be O(n) because we wouldn’t need to require or create any call stack with individual stack frames. Furthermore, the space complexity would be O(1) at best because we can implement an iterative approach using simple variables that would be negligent in terms of how much memory they take up in RAM (Random Access Memory).

Code

Time: O(2^n) | Space: O(n)
Time: O(n) | Space: O(n)
Time: O(n) | Space: O(1)

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

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
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com