The O(lg n) recursion with memorization algorithm for computing fib(n) can be
directly derived from its formula by repeated application of it.
f(n)=
f(n-1)+f(n-2)=
2*f(n-2)+f(n-3)=f(2)*f(n-2)+f)1)*(n-3)=
3*f(n-3)+2*f(n-4)=f(3)*f(n-3)+f(2)*f(n-4)=
and so on until you reach an expression built with
Immediate idea would be to try to exploit
https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
and its representation. This yields the memoization trick from above. If
done correctly, it might be possible to get the O(lg n) run-time which
would be highly desired.
On Tue, May 15, 2018 at 6:
