For equation F(x) = F(x1) + F(x2) + ( F(x1) * F(x2) ) given F(0) and F(1) can we calculate F(n) in log(n) time? asked 19 Feb, 19:40

Well, you can just define $G(x) = F(x)+1$, which has the recurrence relation $G(x) = G(x1)G(x2)$, which you can calculate in $\log(n)$ time. answered 20 Feb, 23:29
Wow..... How did you got this logic ??
(21 Feb, 00:57)
I see it's available on math. stack exchange
(21 Feb, 01:05)
@theoneyowwant how to calculate G(x) = G(x1)G(x2) in log(n) time?
(21 Feb, 10:06)
It's just Fibonacci in power... Take log and see the pattern... Then use matrix exponentiation as shared by @sagar2405
(21 Feb, 10:09)
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...
(21 Feb, 10:10)
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.
(21 Feb, 12:05)
1
Its not from a ongoing contest , its from a past contest i cam across ..
(22 Feb, 13:34)
showing 5 of 7
show all

We can easily found f(n) in O(n) time,but not sure about O(logn). answered 20 Feb, 22:13
yeah O(n) is pretty simple but the problem required log(n) or something similar . 0 < n < 10^8..
(20 Feb, 23:07)
This problem is similar of finding nth Fibonacci in O(logn) time. I found this, https://www.geeksforgeeks.org/programfornthfibonaccinumber/ , in which we can find fibonnaci in O(logn) time. Hope this might help.
(20 Feb, 23:28)

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. answered 21 Feb, 01:16
