Solving Occurrences

The objective of solving occurrences is to find out what the $T_{w o r s t} (n)$ is for a certain algorithm.

Induction

Example

Recursion Tree

Although you can use the substitution method to provide a succinct proof that a solution to a recurrence is correct, you might have trouble coming up with a good guess. In a recursion tree, each node represents the cost of a single sub-problem somewhere in the set of recursive function invocations. We sum the costs within each level of the tree to obtain a set of per-level costs, and then we sum all the per-level costs to determine the total cost of all levels of the recursion. [1]

We focus on formulas such as:

T (n) = {\begin{matrix} 1 & if n = 1 \\ T (n) = a T (n / b) + c f (n) & if n > 1 \end{matrix}

T (n) = {\begin{matrix} 1 & if n = 1 \\ T (n) = a T (n / b) + j T (n / k) + c f (n) & if n > 1 \end{matrix}

Where

Inside the occurrences $T ()$ we have diminishing functions (i.e. division or subtractions)
$a, b, c, j, k \in R$ are constants.

0 - Some notation first

Notation	Meaning	Notes
$T (n)$	$T_{w o r s t} (n)$ , the total complexity
$i_{T (n)}$	Count of internal nodes for $T (n)$
$f_{T (n)}$	Count of leaf nodes for $T (n)$
$i$	Some level $i$ of the tree
$a^{f (i)}$	Count of nodes at a level $i$	It can be written differently
$w_{i}$	Weight of a level $i$	Sum of the weights/complexity of the nodes of a level $i$
$n / b^{i}$	Dimension of a subproblem at level $i$	If not unique, use the one to achieve the longest path from root
$c f (n / b^{i})$	Contribution of one call at a level $i$ to $T (n)$	If not unique, find the maximum cost of a level $O (M a x (w_{i}))$
$n / b^{i} = 1 \leftrightarrow i = \log_{b} (n)$	Total count of levels	Can be replaced with $O (longest path from root)$
$a^{g (i)} \cdot c f (n / b^{i})$	Cost of the nodes at a level $i$	Only if tree is balanced and the terms are unique

Do not get confused with the formulas above, we change variables based on the case.

1 - Construct a tree with $[0 - 2]$ levels

Start by drawing a tree

Draw the root as $c f (n)$ (remember that $f (n)$ can be seen as everything that is not some occurrence $k T (j (n))$ )
- Ex: $f (n) = n^{2}$ and $c = 3$ , would be $3 (n^{2})$ is the root
Draw the branches
- Depending on what the constants $a$ and $b$ are, we need to draw $a + b$ sub-branches for each internal node
- Obviously we need to apply the functions $g (n)$ and $h (n)$ respectively.
  - ex: $a = 2$ and $g (n) = n / 2$ would result in 2 sub-nodes $c (f (g (n))) = 3 ((n / 2)^{2})$
  - ex: $a = 3$ and $h (n) = n / 4$ would result in 3 sub-nodes $c (f (h (n))) = 3 ((n / 4)^{2})$
  - We would have 5 branches for each node, until we reach the case $n = 1$

c + + / / C a s e T (n) = g (n) + h (n) + n^{2} / / f (n) = n^{2} / / O n l y a + b = 1 + 1 s u b - n o d e s [n]^{2} / / L e v e l 0 / [g (n)]^{2} [h (n)]^{2} / / L e v e l 1 / / [g (g (n))]^{2} [h (g (n))]^{2} [g (h (n))]^{2} [h (h (n))]^{2} / / L e v e l 2 T (1) T (1) . . . T (1) / / B o t t o m l e v e l

2 - Create a table for the analysis

We want to create a table for further analysis:

The number of the level, $i$
- Just enumerate the levels
The total count of nodes for that level: How many nodes can we see at a level $i$ ?
- Try to find a pattern and express it as a function of the level with the constant preceding the occurrence, i.e. $a^{i}$
- if it is not possible we might need to look at the height later
- ex: 2 for binary trees (which are usually the case) $2^{0} = 1$ , $2^{1} = 2$ , $2^{2} = 4, \dots$
Weight of the level, the sum of the weight of each node at a level $i$
- Just sum the weight of the nodes and express it a function of the level multiplied by $f (n)$ , $h (i) * f (n)$
- This is important since we discover how fast the tree goes to base case.

Level $i$	Total Nodes at level $i$	Weight of level $i$
0	$a^{i}$	sum the weights on the same level
1
2
3
...	...	...

3 - Analyze the balance of the tree

By now we should have noticed some aspects of our tree.

Look at the table: does the weight of a level change?
- Yes, the weight diminishes so we need to sum all the weights of the nodes to find our $T (n)$ (Case 2)
- No, we can identify the weight of one level and the number of levels to get our answer (Case 1).
Identify a diminishing factor $n / b^{i}$ : does the weight of a sub-problem change homogeneously?
- Yes, the weight of a node is $n / b^{i}$ at some level $i$ (Case 2).
- No, we need to guess the maximum cost of a level (Case 3)
Find the height $i$ : when is the tree going to reach its leaves?
- If there's a diminishing factor, then we can set $n / b^{i} = 1$ and find the count of levels $i$ (Case 2)
- Else we need to find the longest path from the root to the leaves (Case 3)

4 - Guess the case

Case	Critical points	Formula
1 - Balanced Tree, with non-changing weight	$f (n / b^{i})$ is the same, $w_{i}$ does not change	$T (n) = a \cdot T (n / b) + c \cdot f (n)$
2 - Balanced Tree, with homogeneously decreasing weight	$f (n / b^{i})$ is the same, $w_{i}$ decreases	$T (n) = a \cdot T (n / b) + c \cdot f (n)$
3 - Unbalanced Tree, with heterogeneously decreasing weight	$f (n / b^{i})$ is NOT the same, $w_{i}$ decreases	$T (n) = a \cdot T (n / b) + j \cdot T (\frac{n}{k}) + c \cdot f (n)$

And the follow the instructions

{\begin{matrix} Case 1 & T (n) = \sum_{k = 0}^{i} w_{i} = w_{i} \cdot i \\ Case 2 & T (n) = \sum_{k = 0}^{i - 1} a^{k} c f (n / b^{k}) + Θ (a^{i} \cdot T (1)) \\ Case 3 & T (n) = O (M a x {Cost of a level} \cdot Length longest path) \end{matrix}

5.1 - Case 1

Find the diminishing factor
1. $n / b^{i}$
Set it to 1 and find $i$
1. $n / b^{i} = 1 \leftrightarrow i = l o g_{b} (n)$
Find the number of levels
1. $i + 1$ , since the levels start from $0, 1, \dots, l o g_{b} (n)$
Find the weight of a level $w_{i}$
1. Sum the single contributions to the total complexity, for a level

T (n) = \sum_{k = 1}^{i + 1} w_{i} = w_{i} \cdot i + 1

5.2 - Case 2

Find the diminishing factor
1. $n / b^{i}$
Set it to 1 and find $i$
1. $n / b^{i} = 1 \leftrightarrow i = l o g_{b} (n)$
Find the number of leaves
1. $a^{i}$

T (n) = Cost of internal nodes + Cost of leaves = \sum_{k = 0}^{i - 1} a^{k} c f (n / b^{k}) + Θ (a^{i} \cdot T (1))

Remember that, for geometric series:

\sum_{j = 0}^{i} x^{i} = \frac{x^{i + 1} - 1}{x - 1}

and when the summation is infinite and $| x | < 1$ , we have the infinite decreasing geometric series:

\sum_{j = 0}^{inf} x^{j} = \frac{1}{1 - x}

Which we can use since we allow ourselves for a small amount of sloppiness

5.3 - Case 3

Find the maximum cost of a level
Find the length of the longest path from the root , which is given by the branch which diminishes the slowest among all the other ones.

T (n) = O (M a x (Cost of a level) \cdot Length longest path)

Example

Iteration Method

Example

Substitution Method

Example

Master Theorem

The master theorem is a powerful way to solve the occurrences of divide et impera algorithms:

T (n) = T_{s p l i t} (n) + T_{m e r g e} (n) + T_{s o l v e} (n)

Where:

$T_{s p l i t} (n)$ and $T_{m e r g e} (n)$ are not recursive.
- $f (n) = T_{s p l i t} (n) + T_{m e r g e} (n)$ and $f (n) \geq 0$
$T_{s o l v e} (n)$ can be expressed as summation of the time needed to solve the sub-problems
- $\sum T (n_{i}) for i = 1, \dots, k$ which is equal to $a \cdot f (n / b)$

Theorem 4.1 - Master Theorem

Let $a \geq 1$ and $b > 1$ be constants, let $f (n)$ be a function, and let $T (n)$ be defined on the non-negative integers by the recurrence ( $n \in N$ )

T (n) = a T (n / b) + f (n)

where we interpret $n / b$ to mean either $⌊ n / b ⌋$ or $⌈ n / b ⌉$ . Then $T (n)$ has the following asymptotic bounds:

If $f (n) = O (n^{l o g_{b} a - ϵ})$ , for some constant $ϵ > 0$ , then $T (n) = Θ (n^{l o g_{b} a})$
If $f (n) = Θ (n^{l o g_{b} a})$ , then $T (n) = Θ (n^{l o g_{b} a} \log (n))$
If $f (n) = Ω (n^{l o g_{b} a + ϵ})$ , for some constant $ϵ > 0$ , and if $a f (n / b) \leq c f (n)$ for some constant $c < 1$ and all sufficiently large $n$ , then $T (n) = Θ (f (n))$

Explaining the conditions

We need to express the $T (n)$ of the algorithm we want to analyze through the following form:

T (n) = a \cdot T (n / b) + f (n)

Plus, the following conditions must stand true:

$a \geq 1$ , is a constant expressing the number of occurrences
$n / b$ , the dimension of the sub-problem is constant
$b > 1$
$f (n) \geq 0$ for n sufficiently large

If the conditions are met, then we can add the following notation:

$d = \log_{b} (a)$
$g (n) = n^{d} = n^{l o g_{b} (a)}$

Through the theorem we asymptotically compare $g (n)$ and $f (n)$ to discover $T (n)$ . For this we identify the right case:

Case	Condition	Asymptotic Notation	Procedure	Solution
1	$f (n) \leq n^{d}$	$f (n) = O (n^{d - ϵ})$ with $ϵ > 0$	Find $ϵ$	$T (n) = Θ (n^{d})$
2	$f (n) \approx n^{d}$	$f (n) = Θ (n^{d})$	None needed	$T (n) = Θ (n^{d} \log (n))$
3	$f (n) \geq n^{d}$	$f (n) = Ω (n^{d + ϵ})$ with $ϵ > 0$	Find the only $ϵ$ , then find the $c$ such that $\exists c < 1 ∋^{'}$ for n suffic. large $a f (n / b) \leq c f (n)$	$T (n) = Θ (f (n))$

Master Theorem Demonstration

We know that for a divide-et-impera algorithm, we can rewrite its complexity as:

T (n) = T_{s p l i t} (n) + T_{m e r g e} (n) + T_{s o l v e} (n) = f (n) + T_{s o l v e} (n) = f (n) + a T (n / b)

And if the conditions mentioned above are met, we can focus on comparing $f (n)$ with $g (n) = n^{d}$ .

But why do we want to do this?

This is what the demonstration is for.

1 - Rewrite $T (n)$

Through the occurrences tree we try to rewrite $T (n)$ in an explicit way, that is non-recursive.

mastertheoremdem

And we want to focus on finding out:

$a \geq 1$ , the number of sub-problems of dimension $n / b$ with $b > 1$
$a^{i}$ , the number of nodes at a level $i$
$n / b^{i}$ , the dimensionality of the sub-problems at a level $i$
$f (n / b^{i}) with i \geq 0$ , the contribution of one call at a level $i$ to the total complexity
$a^{i} \cdot f (n / b^{i})$ , the complexity of all nodes at a level $i$

We can define the total complexity as the sum of the complexity of all levels:

T (n) = Total complexity of all levels = T_{lvl 1} + T_{lvl 2} + \dots + T_{lvl i} = \sum_{i = 0} a^{i} f (n / b^{i})

The summation lacks a boundary condition. We need to find it.

When does the summation stop?
- When the tree reaches its leaves
Then we need to set $n / b^{i} = 1$ since when sub-problem reaches the size of $1 \to T (1)$ .

n / b^{i} = 1 ⟺ b^{i} = n ⟺ l o g_{b} (n) = i

We assume that $n$ is a power of $b$ , else we would need to use the ceil integer value of $i$

$i \in N$ , represents the levels of the tree. We can now explicitly write $T (n)$ in a non recursive way:

T (n) = \sum_{i = 0}^{l o g_{b} (n)} a^{i} f (n / b^{i})

Since $a^{i}$ is the number of nodes at a level $i$ , the number of leaves is exactly $a^{l o g_{b} (n)}$ which, by the property of the logarithms for the change of the base (prop 1),

l o g_{a} (b) = l o g_{c} (b) \cdot \frac{1}{l o g_{c} (a)}

and the property of inversion (prop 2)

l o g_{a} (b) = \frac{1}{l o g_{b} (a)}

changes its power

l o g_{b} (n) \overset{p r o p 1}{⟹} l o g_{a} (n) \cdot \frac{1}{l o g_{a} (b)} \overset{p r o p 2}{⟹} l o g_{a} (n) \cdot l o g_{b} (a)

and becomes

a^{l o g_{b} (n)} = a^{l o g_{a} (n) \cdot l o g_{b} (a)} = (a^{l o g_{a} (n)})^{l o g_{b} (a)} \overset{d e f}{⟹} n^{l o g_{b} (a)} \overset{d e f}{⟹} n^{d}

We conclude that

a^{i} = n^{d} is the number of leaves

Now, if we want to compute the total recursive calls/nodes, we can use a geometric series:

\sum_{i = 0}^{l o g_{b} (n)} a^{i}

by the property of the geometric series:

\sum_{i = 0}^{k} q^{i} = \frac{q^{k + 1} - 1}{q - 1}

we obtain

\sum_{i = 0}^{l o g_{b} (n)} a^{i} \overset{p r o p}{⟹} \frac{a^{l o g_{b} (n) + 1} - 1}{a - 1} = \frac{a^{l o g_{b} (n)} \cdot a - 1}{a - 1} = \frac{n^{d} \cdot a - 1}{a - 1} \approx Θ (n^{d})

We conclude that $n^{d}$ is not just the number of leaves, but is the factor that dictates the asymptotic growth of the total complexity, since it is also the total count of nodes/recursive calls.

This precisely why, through the master theorem we compare

The number of recursive calls $n^{d} = g (n)$
And the time used for splitting and merging $T_{split + merge} = f (n)$

We want to check which one of the terms is asymptotically dictating the complexity of the algorithm

2 - Find the right case

Remember that we found the following:

T (n) = \sum_{i = 0}^{l o g_{b} (n)} a^{i} f (n / b^{i})

2.1 - Case 1

Hypothesis

2.2 - Case 2

Hypothesis

2.3 - Case 3

Hypothesis

Example

Credits

[1] Introduction to Algorithms, Third Edition
- Publisher: The MIT Press
- Authors: Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford

Solving Occurrences ​

Induction ​

Example ​

Recursion Tree ​

0 - Some notation first ​

1 - Construct a tree with [0−2] levels ​

2 - Create a table for the analysis ​

3 - Analyze the balance of the tree ​

4 - Guess the case ​

5.1 - Case 1 ​

5.2 - Case 2 ​

5.3 - Case 3 ​

Example ​

Iteration Method ​

Example ​

Substitution Method ​

Example ​

Master Theorem ​

Theorem 4.1 - Master Theorem ​

Explaining the conditions ​

Master Theorem Demonstration ​

1 - Rewrite T(n) ​

2 - Find the right case ​

2.1 - Case 1 ​

2.2 - Case 2 ​

2.3 - Case 3 ​

Example ​

Credits ​

Solving Occurrences

Induction

Example

Recursion Tree

0 - Some notation first

1 - Construct a tree with $[0 - 2]$ levels

2 - Create a table for the analysis

3 - Analyze the balance of the tree

4 - Guess the case

5.1 - Case 1

5.2 - Case 2

5.3 - Case 3

Example

Iteration Method

Example

Substitution Method

Example

Master Theorem

Theorem 4.1 - Master Theorem

Explaining the conditions

Master Theorem Demonstration

1 - Rewrite $T (n)$

2 - Find the right case

2.1 - Case 1

2.2 - Case 2

2.3 - Case 3

Example

Credits