Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Can every recurrence relation be converted to a O(1) formula?

Revision en1, by _Muhammad, 2019-01-01 16:40:24

I can convert some simple recurrence relation to a mathematical formula.

Example: F(n) = n + F(n-1), if n > 0 and F(0) = 0; This recurrence relation can be converted into the formula: F(n) = (n*(n+1))/2

But for many other recurrence relations I am unable to do so.
Example: Lets consider the fibonacci sequence. F(n) = F(n-1) + F(n-2), if n > 1 and F(0) = 0, F(1) = 1; I tried hard to convert this recurrence relation to a formula, but failed.

So, my question is it actually possible to convert every recurrence relation to a O(1) formula? If not, then how do I determine that the recurrence relation does not have an implicit formula? If yes, then is there any rule of thumb for converting?

Tags recurrence relation, formula, conversion


  Rev. Lang. By When Δ Comment
en1 English _Muhammad 2019-01-01 16:40:24 845 Initial revision (published)