$\Theta \rho ϵ\eta \Pi \alpha \tau \pi$

Let $a,b\in ℝ$ such that $a\ge 1$ and $b>1$ and let $T,f:{\mathbb{N}}^0\to {ℝ}^{\ge 0}$ be defined such that $$T\left(n\right):=aT\left(\frac{n}{b}\right)+f\left(n\right)$$ Then the following statements are true

• If $f\in 𝒪\left(n^{{\log }_{b}a-ϵ}\right)$ for some $ϵ\in {ℝ}^{>0}$, then $T\left(n\right)\in \mathrm{\Theta }\left(n^{{\log }_{b}a}\right)$
• If $f\in \mathrm{\Theta }\left(n^{\log ba}\right)$ then $T\left(n\right)\in \mathrm{\Theta }\left(n^{\log ba}\ln \left(n\right)\right)$
• If $f\in \mathrm{\Theta }\left(n^{{\log }_b\left(a\right)+ϵ}\right)$ for some constant $ϵ\in {ℝ}^{>0}$ and the function $f^{\prime }\left(n\right):=af\left(\frac{n}{b}\right)$ is eventually dominated up to a constant $c\in ℝ$ by $cf$ where $c<1$, then $T\left(n\right)\in \mathrm{\Theta }\left(f\right)$