Recurrence Equations

We'll analyzer the computational cost of the following recursive search algorithm.

def search(list, value, index=0):
    if list[index] == value:
        return index;

    if index == len(list) - 1:
        return None

    return search(list, value, index + 1)

The first step, requires writing out a system of the equation and the base case of the algorithm.

${T (n) = T (n - 1) + θ (1) T (1) = θ (1)$

Now let's solve the equation, in four different methods.

Iterative

Idea: - develop the equation and express it as sum of terms depending on $n$ and the base case.

Difficulty: - many algebric calculations to do.

$T (n) = T (n - 1) + θ (1) ⟹ T (n) = [T (n - 2) + θ (1)] + θ (1) ⟹ T (n) = {[T (n - 3) + θ (1)] + θ (1)} + θ (1) ⟹ T (n) = T (n - k) + k θ (1)$

Then we calculate the equation when $n - k \to 1$ , the base case.

$n - k = 1 ⟹ k = n - 1 ⟹ T (n) = T (1) + (n - 1) θ (1) ⟹ T (n) = θ (1) + n θ (1) - θ (1) ⟹ T (n) = θ (n)$

Tree

TODO: draw trees in markdown!

Substitution

Idea: - ipothize a solution for the given recurrence equation - verify (by induction) wether it works

Difficulty: - it's hard to find a solution as close as possible to the real solution - it's used mainly in demonstrations

Let's suppose $T (n) = c n$ , and $T (1) = d$ , where $c$ and $d$ are fixed constants.

$T (n) = c n = c (n - 1) + θ (1) ⟹ c n = c n - c + θ (1) ⟹ c = θ (1)$

This doesn't mean that T(1), which is a $θ (1)$ is the same as $c$ , so we need two constants.

${T (n) = T (n - 1) + c T (1) = d$

Now we have to prove that $kn$ is a $O (n)$ and a $ω (n)$ using induction.

$O (n)$

$T (n) = O (n) ⟹ T (n) \leq kn$ where k is to be determined.

Base Case

First, check for which values the base case is verified.

$T (1) \leq k \cdot 1 ⟹ d \leq k ⟹ k \geq d$

Induction

Then check if the general case is covered by the base case.

$T (n) \leq k (n - 1) + c = kn - k + c \leq kn ⟹ k > c$

We get that $k \geq d \land k \geq c$ , we can always find constants $c$ and $d$ so that $\exists k$ greater than both, so the induction is verified.

$ω (n)$

$T (n) = ω (n) ⟹ T (n) \geq kn$ where k is to be determined.

Base Case

First, check for which values the base case is verified.

$T (1) \geq k \cdot 1 ⟹ d \geq k ⟹ k \leq d$

Induction

Then check if the general case is covered by the base case.

$T (n) = k (n - 1) + c = kn - k + c \geq kn ⟹ k \leq c$

We get that $k \leq d \land k \leq c$ , we can always find constants $c$ and $d$ so that $\exists k$ smaller than both, so the induction is verified.

Main

Idea: - It's a set of formulas to solve a recurrence equation

Difficulty: - works only when the equation is in the form $T (n) = a T (\frac{n}{b}) + f (n)$ with $T (1) = θ (1)$

Theorem

Given

$a \geq 1, b \geq 1$
$f : R \to R$
$n \to + \infty lim f (n) \geq 0$

The equation:

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

There are three cases that can generate by comparing $f (n)$ with $n^{l o g_{b} a}$ :

$f (n) = O (n^{l o g_{b} a - ϵ}), ϵ > 0 ⟹ T (n) = θ (n^{l o g_{b} a})$
$f (n) = θ (n^{l o g_{b} a}), ⟹ T (n) = θ (n^{l o g_{b} a} lo g n)$
$f (n) = ω (n^{l o g_{b} a + ϵ}), ϵ > 0 \land a \cdot f (\frac{n}{b}) \leq c f (n), c < 1, n >> 1 ⟹ T (n) = θ (f (n))$

The comparison must be polynomial, by an order of $n^{ϵ}$ .

Where not to apply it?

In the following examples, the main method cannot be applied.

Ex 1

${T (n) = 2 T (\frac{n}{2}) + θ (n lo g n) T (1) = θ (1)$

$a = 2, b = 2$
$f (n) = θ (n lo g n)$
$n^{l o g_{b} a} = n^{l o g_{2} 2} = n$

In this case, $f (n)$ is asintotically bigger than n, but not plynomially bigger. In fact $lo g n < n^{ϵ}, ϵ > 0$

Ex 2

${T (n) = 2 T (\frac{n}{2}) + θ (\frac{n}{l o g n}) T (1) = θ (1)$

$a = 2, b = 2$
$f (n) = θ (\frac{n}{l o g n})$
$n^{l o g_{b} a} = n^{l o g_{2} 2} = n$

In this case, $f (n)$ is asintotically smaller than n, but not plynomially smaller. In fact $lo g n < n^{ϵ}, ϵ > 0$

Computer Science @ Sapienza