\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}