Abdul Bari Algorithms - Recurrence Relation and Master's Theorem for Dividing Functions

Dividing Recurrence Relation 1

function test(n){
if (n>1){
  console.log(n);
  test(n/2);
}
}

When a function takes a parameter n, it can make it smaller by either subtracting like $n-1$ or dividing like $n/2$ or $\sqrt{n}$

Amount of work is $T(n)=T(n/2)+1$

Recurrence Relation Dividing

$T(n)=\{\begin{array}{ll}1& \text{when }n=1\\ 2T(n/2)+n& \text{when }n>1\end{array}$

Tree Method

1 unit of work per level, k steps, which is how many levels

Assume $\frac{n}{2^k}=1$

Simplify to $n=2^k$

Then simplify again to $k=lo{g}_2(n)$, which is the number of levels

Since there’s one unit of work per level, the number of levels is the total units of work

$O(log(n))$

Substitution Method

Original Equation $T(n)=T(n/2)+1$

Plug in $n/2$

$T(n/2)=T(n/2^2)+1$

$T(n)=[T(n/2^2)+1]+1$

$T(n)=T(n/2^2)+2$

$T(n)=T(n/2^3)+3$

Generalized to

$T(n)=T(n/2^k)+k$

Assume $\frac{n}{2^k}=1$

$n=2^k$ and $k=log(n)$

$T(n)=T(1)+log(n)$

$T(n)=1+log(n)$

Answer $O(log(n)$

Dividing Recurrence Relation 2

Recurrence Relation

$T(n)=\{\begin{array}{ll}1& \text{when }n=1\\ T(n/2)+n& \text{when }n>1\end{array}$

Tree Method

Each level does $\frac{n}{2^k}$ amount of work

So for each level, $n+\frac{n}{2}+\frac{n}{2^2}+\frac{n}{2^3}+...+\frac{n}{2^k}$

$n\sum _{i=0}^k\frac{1}{2^i}$

This simplifies to n * 1

so answer is $O(n)$

Substitution Method

$T(n)=T(n/2)+n$

$T(n)=[T(n/2^2)+n/2]+n$

$T(n)=T(n/2^2)+n/2+n$

$T(n)=T(n/2^3)+n/2^2+n/2+n$

$T(n)=T(n/2^k)+T(n/2^{k-1})+T(n/2^{k-2})+...+n/2+n$

Assume $\frac{n}{2^k}=1$

$n=2^k$

$k=log(n)$

$T(n)=T(1)+n[\frac{1}{2^{k-1}}+\frac{1}{2^{k-2}}+...+1/2+1]$

$T(n)=1+n[1+1]$

$T(n)=1+2n$

Answer $O(n)$

Dividing Recurrence Relation 3

function test(n){
if (n>1){
  for (let i=0; i< n; i++){
    console.log(n);
  }
  test(n/2);
  test(n/2)
}
}

The recurrence relation is $T(n)=2T(n/2)+n$

$T(n)=\{\begin{array}{ll}1& \text{when }n=1\\ 2T(n/2)+n& \text{when }n>1\end{array}$

Tree Method

Each row adds up to $n$ amount of work

2nd row as 2 $n/2$s

3rd row has 4 $n/4$s

each row is $\frac{n}{2^k}$

How many rows are there? and in each row how much work is being done?

so n work being done k times

Assume $\frac{n}{2^k}=1$

$n=2^k$

$k=log(n)$

So total amount of work is $n\ast log(n)$

Substitution Method

$T(n)=2T(n/2)+n$

Plug in $(n/2)$

$T(n/2)=2T(n/2^2)+n/2$

Substitute $T(n/2)$ into the original equation

$T(n)=2[2T(n/2^2)+n/2]+n$

Repeat for k times

$T(n)=2^k\ast T(\frac{n}{2^k})+kn$

Assume $T(\frac{n}{2^k})=T(1)$

$\frac{n}{2^k}=1$

$k=log(n)$

Master’s Theorem for Dividing 1

$T(n)=a\ast T(\frac{n}{b})+f(n)$

Assume $a>=1$ and $b>1$

$f(n)=O(n^k\ast log(n{)}^p)$

Case 1

if $lo{g}_b(a)>k$ then $O(n^{lo{g}_b(a)})$

Case 2

if $lo{g}_b(a)=k$

Case 2.1

if $p>-1$ then $O(n^k\ast log(n{)}^{p+1})$

Case 2.2

if $p=-1$ then $O(n^k\ast log(log(n))$

Case 2.3

if $p<-1$ then $O(n^k)$

Case 3

if $lo{g}_b(a)>k$

Case 3.1

if $p>=0$ then $O(n^k\ast log(n{)}^p)$

Case 3.2

if $p<0$ then $O(n^k)$

Examples

Case 1

Example 1

$T(n)=2T(n/2)+1$

$a=2$

$b=2$

$f(n)=O(1)$

$f(n)=O(n^0\ast log(n{)}^0)$

$k=0$, $p=0$

$lo{g}_2(2)=1$ which is bigger than $k$ so it is case 1

$O(n^1)$

Example 2

$T(n)=4T(n/2)+n$

$lo{g}_2(4)=2$, $k=1$, $p=0$

$lo{g}_2(4)=2$ which is bigger than k (1) so case 1

$O(n^2)$

Example 3

$T(n)=8T(n/2)+n$

$lo{g}_2(8)=3$ > $k=1$

Also case 1, so $O(n^3)$

Example 4

$T(n)=8T(n/2)+n^2$

$lo{g}_2(8)=3$ > $k=2$

Still case 1, so $O(n^3)$

Example 5

$T(n)=9T(n/3)+1$

$lo{g}_3(9)=2$ > $k=0$

case 1, so $O(n^2)$

Case 2

Example 1

$T(n)=2T(n/2)+n$

$lo{g}_2(2)=1$ and $k=1$

They’re equal so case 2

No $log(n)$ in $f(n)$, which is just $n$ (original formula $f(n)=O(n^k\ast log(n{)}^p)$

so $p=0$

$O(n\ast log(n))$

Example 2

$T(n)=4T(n/2)+n^2$

$lo{g}_2(4)=2$ and $k=2$

They’re equal so case 2

so $p=0$

$O(n^2\ast log(n))$

Example 3

$T(n)=4T(n/2)+n^2\ast log(n)$

$lo{g}_2(4)=2$ and $k=2$

They’re equal so case 2

so $p=1$

$O(n^2\ast log(n{)}^2)$

Example 4

$T(n)=8T(n/2)+n^3$

$lo{g}_2(8)=3$ and $k=3$

They’re equal so case 2

so $p=0$

$O(n^3\ast log(n))$

Example 5

$T(n)=2T(n/2)+\frac{n}{log(n)}$

Remember $\frac{n}{log(n)}$ is the same as $n\ast log(n{)}^{-1}$

$lo{g}_2(2)=1$ and $k=1$

They’re equal so case 2

In this case $p=-1$ since it’s in denominator

So case 2.2

$O(n\ast log(log(n))$

Example 6

$T(n)=2T(n/2)+\frac{n}{log(n{)}^2}$

Remember $\frac{n}{log(n)}$ is the same as $n\ast log(n{)}^{-2}$

$lo{g}_2(2)=1$ and $k=1$

They’re equal so case 2

In this case $p=-2$ since it’s in denominator

So case 2.3

$O(n^1)$ or $O(n)$

Case 3

Example 1

$T(n)=T(n/2)+n^2$

$lo{g}_2(1)=0$ < $k=2$

So case 3.1

So $O(n^2)$

Example 2

$T(n)=T(n/2)+n^2\ast log(n)$

$lo{g}_2(3)=2$ < $k=2$

So case 3.1, take the entire $f(n)$

So $O(n^2\ast log(n))$

Example 3

If log is in denominator, then case 3.2

$T(n)=T(n/2)+\frac{n^3}{log(n)}$

$lo{g}_2(3)=2$ < $k=2$

So case 3.2, so just take $n^3$

So $O(n^3)$

Master’s Theorem for Dividing 2

Case 1 Examples

$T(n)=2T(n/2)+1$ -> $O(n^1)$

$T(n)=4T(n/2)+1$ -> $O(n^2)$

$T(n)=4T(n/2)+n^1$ -> $O(n^2)$

$T(n)=8T(n/2)+n^2$ -> $O(n^3)$

$T(n)=16T(n/2)+n^2$ -> $O(n^4)$

Case 2

$T(n)=T(n/2)+1$ -> $O(log(n)$

$T(n)=2T(n/2)+n$ -> $O(n\ast log(n))$

$T(n)=2T(n/2)+n\ast log(n)$ -> $O(n\ast log(n{)}^2)$

$T(n)=4T(n/2)+n^2$ -> $O(n^2\ast log(n))$

$T(n)=2T(n/2)+{n\ast log(n)}^2$ -> $O(n^2\ast log(n{)}^3)$

$T(n)=2T(n/2)+\frac{n}{log(n)}$ -> $O(n\ast log(log(n))$

$T(n)=2T(n/2)+\frac{n}{log(n{)}^2}$ -> $O(n)$

Case 3

$T(n)=T(n/2)+n^1$ -> $O(n)$

$T(n)=2T(n/2)+n^2$ -> $O(n^2)$

$T(n)=2T(n/2)+n^2\ast log(n)$ -> $O(n^2\ast log(n))$

$T(n)=4T(n/2)+n^3\ast log(n{)}^2$ -> $O(n^3\ast log(n{)}^2)$

$T(n)=2T(n/2)+\frac{n^2}{log(n)}$ -> $O(n^2)$

Root Function (Recurrence Relation)

function test(n){
if(n>2) {
  stmt
  test(Math.sqrt(n))
}

$T(n)=\{\begin{array}{ll}1& \text{when }n=2\\ T(\sqrt{n})+1& \text{when }n>2\end{array}$

$T(n)=T(n^{\frac{1}{2}})+1$

$T(n)=T(n^{\frac{1}{2^2}})+2$

$T(n)=T(n^{\frac{1}{2^3}})+3$

Continue for k times

$T(n)=T(n^{\frac{1}{2^k}})+k$

Assume n is in powers of 2

$T(2^m)=T(2^{\frac{m}{2^k}})+k$

Assume $T(n^{\frac{m}{2^k}}=T(2^1)$

$\frac{m}{2^k}=1$

$m=2^k$ and $k=lo{g}_2(m)$

$n=2^m$ and $m=lo{g}_2(n)$

$k=log(lo{g}_2(n))$

$O(log(lo{g}_2(n))$