Lua
Lua copied to clipboard
Implemented nth Fibonacci number using different methods
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:
- O(2^N):
fibonacci_recursive(n)- Recursive approach. - O(N):
fibonacci_dp(n)- Dynamic programming approach. - O(logN):
fibonacci_matrix(n)- Matrix exponentiation approach. - 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!