asharammeena's blog

By asharammeena, history, 2 months ago, In English,

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

I hope you find this article insightful

Thank you and happy coding

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There are more approach, like topdown-DP + DnC <O(log n) time — O(n) space)>

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @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, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Topdown-DP approach
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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