I'm a bit tired of virtually all books deriving the master theorem always using their own variation: They sometimes use inequalities $T(n)< T(\frac{n}{b})+f(n)$, sometimes are more sloppy and use $\mathcal{O}(...)$, sometimes $\Theta(...)$, sometimes only $b=2$ or $f(n)=Cn^d$, and almost never using floor and ceiling (which is the way it is always implemented), except for some overly-generalized way like https://epubs.siam.org/doi/pdf/10.1137/1.9781611976496.15
I decided to go and derive once and for all a master theorem I can use 99% of the times, without having to look at the "cases table", especially when doing mostly implementation, and not academic work. Also with a derivation that is easy to visualise in a recursion tree by setting the upper and lower bounds with the next bigger and next smaller full trees (see derivation).
I'm obviously aware that floors and ceilings in this context don't change the asymptotic behaviour, but books that call themselves "bibles" and should prove it at least once so one has seen it, don't do it either.
I wanted to know if I'm doing it correctly and maybe if there's a way of further simplifying my final term:
Definition
$$T(n) = \left\{\begin{matrix} g(n) && n=1\\ a_LT(\lfloor\frac{n}{b}\rfloor + a_RT(\lceil\frac{n}{b}\rceil) + f(n)&& n>1 \end{matrix}\right.$$
$$ a:=a_L+a_R \\ f(n), g(n) \quad \text{monotone increasing}$$
Derivation $$ \text{Number of leaves of next smaller full tree:}\quad n_-:=b^{\lfloor \log_b n\rfloor}\\ \text{Number of leaves of next bigger full tree:}\quad n_+:=b^{\lceil \log_b n\rceil}$$
$$\begin{matrix} T(n) && = && a_LT(\lfloor\frac{n}{b}\rfloor) + a_RT(\lceil\frac{n}{b}\rceil) + f(n) \\ && \leq && a_LT(\lfloor\frac{n_+}{b}\rfloor) + a_RT(\lceil\frac{n_+}{b}\rceil) + f(n_+) \\ && = && a_LT(\frac{n_+}{b})+ a_RT(\frac{n_+}{b}) + f(n_+) \\ && = && aT(\frac{n_+}{b}) + f(n_+) \\ && = && a(aT(\frac{n_+}{b^2})+f(\frac{n_+}{b})) + f(n_+) \\ && = && \ldots \\ && = && a^k T(\frac{n_+}{b^k}) + \sum\limits_{i=0}^{k-1}a^if(\frac{n_+}{b^i}) \\ && = && a^{\log_b{n_+}} T(1) + \sum\limits_{i=0}^{\log_b{n_+}-1}a^if(\frac{n_+}{b^i}) \\ && = && a^{\log_b{n_+}} g(n) + \sum\limits_{i=0}^{\log_b{n_+}-1}a^if(\frac{n_+}{b^i}) \\ && = && a^{\lceil\log_b{n}\rceil} g(n) + \sum\limits_{i=0}^{\lceil\log_b{n}\rceil-1}a^if(\frac{b^{\lceil \log_b n \rceil}}{b^i}) \\ && \leq && a^{\log_b{n}+1} g(n) + \sum\limits_{i=0}^{\lceil\log_b{n}\rceil-1}a^if(\frac{b^{\lceil \log_b n \rceil}}{b^i}) \\ && \leq && a\cdot a^{\log_b{n}} g(n) + \sum\limits_{i=0}^{\lceil\log_b{n}\rceil-1}a^if(\frac{b^{\lceil \log_b n \rceil}}{b^i}) \end{matrix}$$
Analogously for the lower bound using $n_-$ we get:
$$\begin{matrix} T(n) && = && a_LT(\lfloor\frac{n}{b}\rfloor) + a_RT(\lceil\frac{n}{b}\rceil) + f(n) \\ && \geq && \cdots \\ && \geq && a^{\log_b{n}-1} g(n) + \sum\limits_{i=0}^{\lfloor\log_b{n}\rfloor-1}a^if(\frac{b^{\lfloor \log_b n \rfloor}}{b^i}) \\ && \geq && \frac{1}{a}\cdot a^{\log_b{n}} g(n) + \sum\limits_{i=0}^{\lfloor\log_b{n}\rfloor-1}a^if(\frac{b^{\lfloor \log_b n \rfloor}}{b^i}) \end{matrix}$$
The final most simplified solution without knowing $f(n)$ and $g(n)$ is: $$\boxed{\frac{1}{a}\cdot a^{\log_b{n}} g(n) + \sum\limits_{i=0}^{\lfloor\log_b{n}\rfloor-1}a^if\left(\frac{b^{\lfloor \log_b n \rfloor}}{b^i}\right) \leq T(n) \leq a\cdot a^{\log_b{n}} g(n) + \sum\limits_{i=0}^{\lceil\log_b{n}\rceil-1}a^if\left(\frac{b^{\lceil \log_b n \rceil}}{b^i}\right)} $$
Is this correct and fully simplified? Depending on my $f(n)$ and $g(n)$ I can then work out the bounds for what I'm working with.
E.g. Merge sort: $$a_L = a_R = 1 \\ a = b = 2 \\ g(n) \in \Theta(1) \quad \text{using} \quad C_{g,-}, C_{g,+}, n_g\\ f(n) \in \Theta(n) \quad \text{using} \quad C_{f,-}, C_{f,+}, n_f \\ n_0 := \max\{n_g,n_f\}$$
$$\Longrightarrow \frac{1}{2}\cdot n\cdot g(n) + \sum\limits_{i=0}^{\lfloor\log_2{n}\rfloor-1}2^if\left(\frac{2^{\lfloor \log_2 n \rfloor}}{2^i}\right) \leq T(n) \leq 2\cdot n\cdot g(n) + \sum\limits_{i=0}^{\lceil\log_2{n}\rceil-1}2^if\left(\frac{2^{\lceil \log_2 n \rceil}}{2^i}\right) \\ \Longrightarrow \frac{1}{2}\cdot n\cdot C_{g,-} + \sum\limits_{i=0}^{\lfloor\log_2{n}\rfloor-1}2^iC_{f,-}\frac{2^{\lfloor \log_2 n \rfloor}}{2^i} \leq T(n) \leq 2\cdot n\cdot C_{g,+} + \sum\limits_{i=0}^{\lceil\log_2{n}\rceil-1}2^iC_{f,+}\frac{2^{\lceil \log_2 n \rceil}}{2^i}\\ \Longrightarrow \frac{1}{2}\cdot n\cdot C_{g,-} + C_{f,-}\lfloor\log_2{n}\rfloor 2^{\lfloor \log_2 n \rfloor} \leq T(n) \leq 2\cdot n\cdot C_{g,+} + C_{f,+}\lceil\log_2{n}\rceil 2^{\lceil \log_2 n \rceil} \\ \Longrightarrow \frac{1}{2}\cdot n\cdot C_{g,-} + C_{f,-}(\log_2{n}-1)2^{\log_2{n}-1} \leq T(n) \leq 2\cdot n\cdot C_{g,+} + C_{f,+}(\log_2{n}+1) 2^{\log_2 n +1} \\ \Longrightarrow \frac{1}{2}\cdot n\cdot C_{g,-} + \frac{1}{2}C_{f,-}\cdot n \cdot(\log_2{n}-1) \leq T(n) \leq 2\cdot n\cdot C_{g,+} + 2\cdot C_{f,+}\cdot n \cdot(\log_2{n}+1)$$ $$ \forall n>n_0 \\ \Longrightarrow T(n) \in \Omega(n\log_2n) \cap \mathcal{O}(n\log_2n) \\ \Longrightarrow T(n) \in \Theta(n\log_2n)$$