# 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).

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