__Number Theory - Calculate ‘N__^{th}’ element of recurrence
relation in O(logn)

__Number Theory - Calculate ‘N__

^{th}’ element of recurrence relation in O(logn)
__
__

**Note:**It is recommended to read our previous article on Matrix Exponentiation, as we will be using concept of matrix exponentiation in this article. If you have not yet read it click here to read it.

So, after reading our previous article lets continue with our next article
on ‘finding N^{th} element of recurrence relation in O(logn)’.

So, before diving into this article lets understand first what is
recurrence relation.

**1. **
**
What is recurrence relation?
**
A recurrence relation is an equation that recursively defines a sequence
where the next term is a function of the previous terms (Expressing

*F*as some combination of

_{n}*F*with

_{i}*i*<

*n*).

In simple words it is basically an equation that defines a sequence based on a rule that gives the next term as a function of the previous terms.

**Example:**
Fibonacci series – *Fn *= (*Fn *– 1) + (*Fn *– 2)
where n > 2

base condition: F(1) = 1

F(2) = 1
**
**

We are often required to calculate or solve problems in which we have to
form a recurrence relation and then proceed accordingly. But, while dealing
with such problems we will definitely be requiring to calculate N ^{th} element of our recurrence relation.

So, it becomes necessary to use best possible approach to get N ^{th }element of recurrence relation.

**
2. Naïve Approach (Brute Force):
**
As you are very much familiar now with what we do in naïve approach, yes we
will be simply iterating from 1

^{St}term to N

^{th }term and getting our required answer, simple right?

But at the same time notice the time complexity of this approach which is O(n) hence it will definitely lead to Time Limit Exceeded(TLE) in most of the problems.

Don’t worry we will optimize this approach and we will manage to get Accepted 😊

**Note**
: We highly recommend you to try out naïve approach by yourself first and
then compare it with our solution, as we are here to make you code better
and efficiently.

before looking at implementation it is important to note that we cannot
write a general code for every recurrence relation hence we will have to
take an example and code for it.

E.g. *Fn *= (*Fn *– 1) + (*Fn *– 2) where n > 2

base condition: F(1) = 1

F(2) = 1

Below is the implementation of naïve approach for above recurrence
relation:

**
Time Complexity: O(n)
**

**3. Optimized Approach – O(logn):**
**
**
So, After looking at brute force approach we will try to optimize our
approach with some of our observation.

let’s understand our observation with a simple example:

E.g.

*Fn***= (**where

*Fn*– 1) + (*Fn*– 2)**n > 2**

base condition

**: F(1) = 1**

F(2) = 1

F(2) = 1

Below is the step by step process to proceed with optimization:

**Step1:**
Firstly, determine the number of elements on which our current term (**i.e F _{n}** ) of recurrence relation depends (

**i.e. K**). K = 2, in our case.

**Step2:**Determine base values or initial values (i.e. F(1) = 1, F(2) = 1 in our case)

**Step3:**Determine Transformation matrix: The transformation matrix in this context is a special matrix with which we will multiply our initial values matrix and based upon the power of transformation matrix we will get terms of our recurrence relation.

**The dimension of transformation matrix is taken as K x K.**

**Note:**
here the power of transformation matrix is calculated using Matrix
Exponentiation, if you want to know more about it click here.

You can visualize this process as below:

Consider F_{1 }and F_{2 }as our initial terms and since in
our case value of k = 2, we will be using a 2 x 2 matrix as a
transformation matrix.

**
Note: Below written equation is true for every linear recurrence
relation.
**

Now, we have got our final equation to calculate N^{th }element of
recurrence relation.

**Note:**
here the power of transformation matrix is calculated using Matrix
Exponentiation, if you want to know more about it click here.

Below is the implementation of optimized approach for above recurrence
relation:

**Time Complexity: O(logn)**

It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.

So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.

1. **Problem from Programmers Army: **Try writing code for finding N^{th} term of this recurrence relation
**F(n) = 2F _{n-1 }+ 3F_{n-2}** for n > 2

F(1) = 2, F(2) = 3;

We highly recommend to solve above problems if you got stuck read this article once again.

So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!

**
**

** **

** **

** **

** **

** **

**Happy Coding **

**By Programmers Army **
**😊**