For equation F(x) = F(x-1) + F(x-2) + ( F(x-1) * F(x-2) ) given F(0) and F(1) can we calculate F(n) in log(n) time?
We can easily found f(n) in O(n) time,but not sure about O(logn).
Well, you can just define G(x) = F(x)+1, which has the recurrence relation G(x) = G(x-1)G(x-2), which you can calculate in \log(n) time.
I found it online that F(n) = 2^{Fib(n)}-1 when f(0)=0 and f(1)=1. And 2^{fib(n)} can be calculated in logn.
But it is special case. For the generalized version, @theoneyouwant wrote the perfect answer.
yeah O(n) is pretty simple but the problem required log(n) or something similar . 0 < n < 10^8…
This problem is similar of finding nth Fibonacci in O(logn) time. I found this, Program for Fibonacci numbers - GeeksforGeeks , in which we can find fibonnaci in O(logn) time. Hope this might help.
Wow… How did you got this logic ??
Awesome…
I see it’s available on math. stack exchange
@theoneyowwant how to calculate G(x) = G(x-1)G(x-2) in log(n) time?
It’s just Fibonacci in power… Take log and see the pattern… Then use matrix exponentiation as shared by @sagar2405
I hope it’s not a question for an ongoing contest… Otherwise you can be banned from discuss site… Please delete this post in case it’s for an ongoing contest…
Well, I just thought of this myself, since it’s somewhat similar to think of it as a functional equation, where such transforms are quite common. In general, you can try such substitutions on various reccurences to get a better form/ to solve it faster. You may have also solved some dynamic programming problems where redefinitions give a faster solution.
Its not from a ongoing contest , its from a past contest i cam across …