This is a great solution since it is relatively simple and efficient, as it run in
But, can we do better?
Yes we can!
This one is for the algo-holics and thanks to its simplicity and efficiency, I consider it to be a brilliant solution.
We are going to find the n'th Fibonacci number in
Efficient Power Algorithm
For starters, let's see how we can calculate
in an efficient time complexity of
This algorithm is based on the fact that:
Since this is right for every
, we can claim that:
And now, let's put it all together:
So now, we see that if we want to know the n'th Fibonacci number (and the one before), all we have to do is some matrix multiplication! More specifically, we need to raise a matrix to the power of
. But we already know how to calculate
. This is amazingggg! Note that every matrix multiplication is
So, suppose we adjust our power algorithm to work with matrix multiplication instead of regular multiplication, we can calculate
, then multiply it by
and voilà! We calculated both
Take a minute, let that sink in 😌.
So, after you took a minute to chill out your ecstasy, think about it: Is Fibonacci special? Or this method going to work for all recursive equations like Fibonacci?
Well, while Fibonacci IS special, this method is going to work for all equations similar to Fibonacci. For example, let's define the Zigi sequence as follow:
Z1=7 Z2=−4 Zn=2∗Zn−1−3∗Zn−2
The secret is simple: Just find the correct matrix, and the magic will come. Here, we can see that:
And, as you see, the n'th Zigi's number can be computed in
Thank you for your time ❤️!
For further actions, you may consider blocking this person and/or reporting abuse