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).
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, https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ , in which we can find fibonnaci in O(logn) time. Hope this might help.
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.
3 Likes
Wow… How did you got this logic ??
Awesome…
I see it’s available on math. stack exchange
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.
@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 …
1 Like