Recurrence relation

what is Recurrence relation

In mathematics, a recurrence relation is an equation that expresses the
n -th term of a sequence as a function of the  k  preceding terms.

examples

merge sort

sort(array A, int begin, int end):
 if(begin = end)
	 return;
 sort(A, begin , (begin + end)/2)
 sort(A, ((begin + end)/2)+1, end)
 pivot = (begin + end)/2 
 Merge(A,begin, pivot, end)	 	 

we can represent this algorithm as a recurrence relation in the following way:

this formula is the representation of #merge sort. how ever it should be mention that as learned in Asymptotic notations we can ignore any constant or round value, so lets rewrite the formula as the following:

How can we calculate a Recurrence relation

Recursion tree

lets look at the following relation :

we can calculate $T(n)$ by creating this Recursion tree:

this will continue until $\frac{n}{n}$ and we are looking for the height of the tree in order to solve $T(n)$

so, lets explain whats going on:

• each level of the tree is performing $n$ work
• each branch of a level is performing $\frac{n}{2^b}$ where $b$ is the branch level so in total each branch is performing $2^bֿ\cdot \frac{n}{2^b}$
• as we said this tree will expand until $2^b=n$ there for the height of the tree will be $b=log(n)$.
• now we are performing $\log (n)$ calls where each call perform $n$ work. there fore: $T(n)=\theta (n\cdot \log (n))$

unequal Recursion tree

lets look at the next relation:

where $C_n$ is the non recursive part of the function.

this time the tree is not even as the tree we saw before and it will look something like this:

each level is performing $n$ work as before. how ever the right branches clearly is performing more work. what is going to happen is that the more the tree branches will expand, the more job will be done on the rightmost side of the tree and it will become more and more unbalanced.

as before the tree will end at $\frac{n}{n}$ so that mean the left branch will finish way more quickly.

let's ask our self : so what if the tree is not equal? what will happen? the answer is the following. in the #Recursion tree from before, each branch performed $n$ work.
but that only worked because they were equal. in this case at some point the left branch will finish its work and the right one will continue his.
that means that at some branch $b_i$ what will happen is the following:
$\mathrm{\forall }b\ge b_i$ $work<C_n$

so how to calculate $T(n)$?

• we will divide the tree to 2 parts: the parts where $work=C_n$ and the part where $work<C_n$
  the tree will look something like this:
  

• now we going to calculate the maximum height of the tree in the first part and the maximum height in the second part.

• the first part will be the best case scenario of our function and therefore will be $\mathrm{\Omega }$

• the second part will be the worst case scenario of our function and therefore will be $O$ .

• the equal tree height will be $lo{g}_{3}n$ and the unequal tree height will be $lo{g}_{2/3}n$

• so as we said the first part time complexity will be $\mathrm{\Omega }(n{\log }_{3}n)$ and the second part will be $O(n{\log }_{2/3}n)$ but we know from Asymptotic Analysis that switching between bases is performed by constant and there for the total time complexity of this function will be $\theta (n\cdot \log n)$

Recursion tree with more than 2 branches

lets check the following example:

where $C{n}^2$ is some work inside the function that is non recursive.

the tree will look something like this:

lets see whats going on :

• because the work inside the recursion is divisive each branch will do less work until $T(1)$

• so we need to understand 2 things : the first one is the height of the tree so let's build a formula assuming $b_i$ is the branch $i$ in the tree. and we know that $\text{at branch: }{b}_n\text{the work is: }\frac{n}{n}=1$
  the formula will be as the following :
  at each branch $b_i$ each leaf will do the following job $c(\frac{n}{4^i}{)}^2$ the first $i$ is 0.

• each branch will do the sum of that that will calculate to: $(\frac{3}{16}{)}^i\cdot C{n}^2$

• if we sum all the floors we will get :

• this is a Geometric progression where $q<1$ and therefore it will sum up to a constant.

• the best case scenario is $\mathrm{\Omega }(n^2)$ because that the job the first branch is doing

• because the sum is the worst case scenario and the first work in the best and they are both of $n^2$ the Asymptotic notations of this formula will be : $\theta (n^2)$

Iterative method

in this method we will "open" the formula to get an idea if what will happen at the end. (we need to now the value of $T(1)$ for that but it most of the time will be 1 or 0).

example 1

lets open the formula:

lets see how its sums up in $T(n)$ :

if we try to build it until the end we will get :

notice that $2^{i+1}-2$ is a Geometric progression

how ever, this is not a valid proof and we need to proof it with # Inductive reasoning

• base- $i=1$ we will get $T(n)=2T(n-3)+2$ as needed.
• step- assume that $i=k-1$ and we will prove for $i=k$
  we will use full induction most of the times

continue develop the expression and we will get the above result.
because we know that $T(0)=T(1)=T(2)=T(3)=1$
now assume $i=\frac{n-1}{3}$ and we now get the following : $T(n)=2^{\frac{n}{3}}\cdot T(1)+2^{\frac{n}{3}+1}-2=2^{\frac{n}{3}}+2^{\frac{n}{3}+1}-2\in \theta (2^{\frac{n}{3}})$

positioning method

we will guess what is the big $O$ notation and the $\mathrm{\Omega }$ notation, by guessing i mean we will assume that there is a constant $C$ according to Asymptotic Analysis rules.

• lets assume that $T(n)\in O(n^2)$ which means that $\mathrm{\exists }C,n_0\text{such that: }\mathrm{\forall }n\ge n_0\text{,}T(n)\le C\cdot n^2$
• proof you assumption with inductive reasoning
• do the same for $\mathrm{\Omega }$ if possible.
• try the same for a smaller big $O$ and $\mathrm{\Omega }$

the Master theorem

the master theorem help us solve a specific type of Recurrence relation but is the fastest way from all the above.

for formulas that look like the following:

where $f(n)$ is the root of the function (the non recursive part).
the base for the master theorem is simple find out who from the root or the recursion part does more work.
we can achieve this with the following rules:

case 1:

this is the case where the recursive part works harder than the root

case 2:

this is the case when both the recursive part and the root does the same work

there is an extended case for that one :

case 3:

this case is when the root does more work than the recursive part.

examples:

$T(n)=8T(\frac{n}{4})+n^2$
$f(n)=n^2$ , $a=8,b=4$
${\log }_{b}a={\log }_{4}8=1.5$

$n^{1.5}<n^2\to {\mathrm{\forall }}_{0<ϵ<0.5}:f(n)=n^2=\mathrm{\Omega }(n^{1.5+ϵ})$

therefore:
$T(n)\in \mathrm{\Theta }(f(n))\in \mathrm{\Theta }(n^2)$

$T(n)=9T(\frac{n}{3})+n^2$
$lo{g}_{3}9=2,f(n)=n^2=\mathrm{\Theta }(n^{{\log }_{3}9})$

therefore: $T(n)\in \mathrm{\Theta }(n^{2}logn)$

switching variables method

lets look at the following relation:

this can be a hard expression to develop using the methods above..
we should try make it easier by switching variables:

mark $m=logn$ and notice that: $2^m=n$ now:

this is a recurrence relation we already know $S(m)\in \mathrm{\Theta }(m\cdot logm)$
therefore: