Skip to content

Efficient Fibonacci Implementation: O(logN) #2600

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
anirudhb11 opened this issue Oct 13, 2021 · 3 comments
Closed

Efficient Fibonacci Implementation: O(logN) #2600

anirudhb11 opened this issue Oct 13, 2021 · 3 comments
Assignees
@anirudhb11
Labels
stale

Comments

@anirudhb11
Copy link
Contributor

anirudhb11 commented Oct 13, 2021 •
edited
Loading

Is your feature request related to a problem? Please describe.
Add an efficient implementation for the calculation of Fibonacci Numbers. Present implementations have O(N) time complexity. I would like to add an O(lgN) time complexity solution

Describe the solution you'd like
The approach would make use of matrix exponentiation to compute the nth Fib number

As part of Hacktoberfest 2021, I would like to enhance implementation of this class, could you please assign this to me @siriak.
Thank you
@siriak
Copy link
Member

siriak commented Oct 13, 2021

You should probably make it a separate class from naive implementation

@anirudhb11 anirudhb11 mentioned this issue Oct 14, 2021
Merged
11 tasks
@anirudhb11
Copy link
Contributor Author

@siriak could you please review this.

@github-actions
Copy link

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@github-actions github-actions bot added the stale label Nov 18, 2021
@siriak siriak closed this as completed Nov 18, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@anirudhb11 anirudhb11

Labels
stale
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@siriak @anirudhb11