Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### asharammeena's blog

By asharammeena, history, 2 months ago, ,

Hello guys,

There are various methods to solve Fibonacci sequence problems. But I was not able to find any place where all methods to find Fibonacci were discussed with both proper mathematical explanation and implementation. Therefore, I have written an article for Fibonacci Sequence on my blog which covers all mathematical concepts and implementations and is suitable for beginners.

Topics covered are:-

1. Brute Force approach ( O(2^n) )
2. Dynamic Programming approach ( O(n) )
3. Matrix exponential approach ( O(logn) )
4. Golden number ratio (well explained) ( O(logn) )
5. Analysis of growth of Fibonacci Sequence

Here is the link : Fibonacci Sequence

Thank you and happy coding

• +9

 » 2 months ago, # |   0 There are more approach, like topdown-DP + DnC
•  » » 2 months ago, # ^ |   0 Please write the full form of DnC. I didn't get you. I haven't written about fast doubling method yet. I will soon update the article.
•  » » » 2 months ago, # ^ |   0 DnC = divide and conquer
•  » » 2 months ago, # ^ |   0 @SPyofgame I have written about DP (Bottom Up implementation) which takes O(n) time and space. Please tell me which DP approach are you talking about which takes O(logn) time and O(n) space.
•  » » » 2 months ago, # ^ |   0 Topdown-DP approachll fib(int n) { if (f[n]) return f[n]; if (n < 3) return f[n] = (n + 1) / 2; int k = (n + 1) / 2; return f[n] = fib(k) * fib(k) + fib(k-1) * ((n & 1) ? fib(k-1) : 2*fib(k)); } 
•  » » » » 2 months ago, # ^ |   0 This is known as fast doubling method. Please be more specific. Terms like Topdown-DP and DnC are applicable to multiple solutions. In fact every solution of fibonacci is DnC based. Anyway thanks for the reminder