Matrix exponentiation

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.

3 Likes

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, https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ , 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 …

1 Like