Lua icon indicating copy to clipboard operation
Lua copied to clipboard

Implemented nth Fibonacci number using different methods

Open Gyan172004 opened this issue 2 years ago • 0 comments

This PR introduces enhancements to the Fibonacci sequence calculation in the "Fibonacci.lua" file. It provides implementations for calculating the nth Fibonacci number using four different approaches with varying time complexities:

  1. O(2^N): fibonacci_recursive(n) - Recursive approach.
  2. O(N): fibonacci_dp(n) - Dynamic programming approach.
  3. O(logN): fibonacci_matrix(n) - Matrix exponentiation approach.
  4. O(1): fibonacci_binet(n) - Binet's formula approach.

Details

  • Added comments and explanations for each function.
  • Included assert tests for all four methods to ensure correctness.
  • Reordered the functions from worst to best time complexity for clarity.

Please review and merge this PR to enhance the Fibonacci calculations in codebase.

Thank you!

Gyan172004 avatar Oct 07 '23 21:10 Gyan172004