78 lines
2.6 KiB
Plaintext
78 lines
2.6 KiB
Plaintext
|
\documentclass{article}
|
||
|
|
\usepackage[utf8]{inputenc}
|
||
|
|
\usepackage{amsmath}
|
||
|
|
\title{Simplifying Mathematical Notations in Recurrence Equations}
|
||
|
|
\author{Alessandro Ferro}
|
||
|
|
\date{April 2022}
|
||
|
|
|
||
|
|
\begin{document}
|
||
|
|
|
||
|
|
\maketitle
|
||
|
|
|
||
|
|
\section{Introduction}
|
||
|
|
In the book "Introduction to Algorithms" written by CLRS, section 4.4, the following recurrence equation is given:
|
||
|
|
|
||
|
|
\begin{equation}
|
||
|
|
T(n)=
|
||
|
|
\begin{cases}
|
||
|
|
\Theta(1), & \text{if}\ n=1 \\
|
||
|
|
3T(\lfloor n/4 \rfloor) + \Theta(n^2), & \text{otherwise}
|
||
|
|
\end{cases}
|
||
|
|
\end{equation}
|
||
|
|
|
||
|
|
which later on was simplified as
|
||
|
|
|
||
|
|
\begin{equation}
|
||
|
|
T(n)=
|
||
|
|
\begin{cases}
|
||
|
|
\Theta(1), & \text{if}\ n=1 \\
|
||
|
|
3T(\lfloor n/4 \rfloor) + cn^2, & \text{otherwise}
|
||
|
|
\end{cases}
|
||
|
|
\end{equation}
|
||
|
|
|
||
|
|
we will argue that even if $\Theta(n^2)$ is a set, and $c*n^2$ is a scalar and they generally cannot be swapped one with the other, in this case it can be done and will help the equation to be more tractable.
|
||
|
|
|
||
|
|
\section{Proof}
|
||
|
|
Let's consider the general case only, so we have
|
||
|
|
\begin{gather*}
|
||
|
|
3T(\lfloor n/4 \rfloor) + \Theta(n^2)
|
||
|
|
\end{gather*}
|
||
|
|
|
||
|
|
which expanded is
|
||
|
|
\begin{gather*}
|
||
|
|
3T(\lfloor n/4 \rfloor) + f(n) \ \text{where} \ f(n) \in \Theta(n^2)
|
||
|
|
\end{gather*}
|
||
|
|
|
||
|
|
$f(n) \in \Theta(n^2)$ means that
|
||
|
|
|
||
|
|
$\exists \ c_1>0,c_2>0,n_0>0$ such that $c_1*n^2 \leq f(n) \leq c_2*n^2 \ \forall n \geq n_0$
|
||
|
|
\\ \\
|
||
|
|
So we have
|
||
|
|
\begin{gather*}
|
||
|
|
3T(\lfloor n/4 \rfloor) + c_1 * n^2 \leq 3T(\lfloor n/4 \rfloor) + f(n) \leq 3T(\lfloor n/4 \rfloor) + c_2 * n^2 \ \forall n \geq n_0
|
||
|
|
\\
|
||
|
|
=
|
||
|
|
\\
|
||
|
|
\underbrace{3T(\lfloor n/4 \rfloor) + c_1 * n^2}_{\alpha} \leq T(n) \leq \underbrace{3T(\lfloor n/4 \rfloor) + c_2 * n^2}_{\beta} \ \forall n \geq n_0
|
||
|
|
\end{gather*}
|
||
|
|
So if we resolve $\alpha$ only, we'll have a lower bound for $T(n)$. If we resolve $\beta$ only, we'll have an upper bound for $T(n)$.
|
||
|
|
|
||
|
|
|
||
|
|
But $\alpha$ and $\beta$ are asymptotically equivalent, that means that $T(n)$ is asymptotycally equivalent to $\alpha$ and $\beta$ too.
|
||
|
|
|
||
|
|
So we just need to resolve either $\alpha$ or $\beta$ to obtain the asymptotic value of $T(n)$, so we can just resolve for a generic $c$ :
|
||
|
|
|
||
|
|
\begin{equation}
|
||
|
|
T(n)=
|
||
|
|
\begin{cases}
|
||
|
|
\Theta(1), & \text{if}\ n=1 \\
|
||
|
|
3T(\lfloor n/4 \rfloor) + cn^2, & \text{otherwise}
|
||
|
|
\end{cases}
|
||
|
|
\end{equation}
|
||
|
|
|
||
|
|
since using a generic constant won't change the asymptotic value.
|
||
|
|
|
||
|
|
\section{Conclusions}
|
||
|
|
The concept described in this document and the relative proof can be easily extended to any similar recurrence, and generalized.
|
||
|
|
\end{document}
|