This lecture is going to develop asymptotic notation mathematically and how to solve recurrences.

Asymptotic notation

${ O }$ notation

${ f(n) = O (g(n)) }$ means there are consts ${ c>0, n_0 > 0 }$ such that (assume ${ f(n) }$ is non-negtive)

$$ 0 \leq f(n) \leq cg(n), \text{ for all } n \geq n_0 $$

Ex. ${ 2 n^2 = O(n^3) }$

Notice, ${ f(n) = O (g(n)) }$ doesn’t means ${ g(n) = O(f(n)) }$. The ${ O }$ notation is not asymmetric. Actually, we can treat ${ O(g(n)) }$ as a set of funtions.

$$ O(g(n)) = \left\{ f(n): \text{ there are consts } c>0, n_0 >0 \text{ such that } 0 \leq f(n) \leq cg(n), \text{ for all } n \geq n_0 \right\} $$

So, when we talk about ${ f(n) = O(g(n)) }$, actually, it means ${ f(n) \in O(g(n)) }$

Macro convention

A set in a formula represents an anonymous funtion in that set.

Ex. ${ f(n) = n^3 + O(n^2) }$

That means there is a funtion ${ h(n) \in O(n^2) }$ such that ${ f(n)=n^3+ h(n) }$

Ex. ${ n^2+O(n) = O(n^2) }$

That means for any ${ f(n)\in O(n) }$, there is an ${ h(n)\in O(n^2) }$, such that ${ n^2+f(n)=h(n) }$.

${ \Omega }$ notation

Define: ${ \Omega(g(n)) =\left\{ f(n): \text{ there are consts } c>0, n_0 >0 \text{ such that } 0 \leq g(n) \leq cf(n), \text{ for all } n \geq n_0 \right\} }$

Ex. ${ \sqrt n = \Omega(\lg n) }$

${ \Theta }$ notation

Define: ${ \Theta (g(n)) = O(g(n)) \cap \Omega (g(n)) }$

${ o }$ and ${ \omega }$ notation

Define: ${ o(g(n)) = \left\{ f(n): \text{ for any const } c>0, \text{ there exists const } n_0 >0 \text{ such that } 0 \leq f(n) \leq cg(n), \text{ for all } n \geq n_0 \right\} }$

Define: ${ \omega(g(n)) = \left\{ f(n): \text{ for any const } c>0, \text{ there exists const } n_0 >0 \text{ such that } 0 \leq g(n) \leq cf(n), \text{ for all } n \geq n_0 \right\} }$

Ex. ${ 2n^2 = o(n^3) }$,

Ex. ${ \frac{1}{2}n^2 = \Theta(n^2) }$ but ${ \neq o(n^2) }$

Solving recurrences

Substitution method

1. Guess the form of the solution

2. Verify by induction

3. Solve for consts

Ex. Solve the following recurrences

$$ T(n) = \begin{cases} 4 T(n/2)+n, n>1\\ \Theta(1), n = 1 \end{cases} $$

Ans:

1. Guess: ${ T(n) = O(n^3) }$

2. Induction: Assume ${ k<n }$ is correct, that is

$$ T(k) \leq ck^3 \text{ for } k < n $$

1. Now, let’s check

$$ T(n) = 4T(n/2) +n \leq 4c(n/2)^3+n = \frac{c}{2}n^3+n $$

So, ${ T(n) \leq cn^3 - \left(\frac{c}{2}n^3-n\right) }$, which at most ${ cn^3 }$ when ${ \frac{c}{2}n^3-n \geq 0}$. That is we can find ${ c }$ and ${n_0 }$, such that ${ T(n) \in O(n^3) }$, e.g. ${ c\geq1, n_0=1 }$

The base case is trivial, it’s easy to find some sufficient large ${ c }$, such that

$$ T(1)=\Theta(1) \leq c $$

Actually, the above proof is from the class video, I thought it's not rigour mathematically. Therefore I will show another proof in the following.

Let ${ C=\max \left\{\frac{1}{2},\Theta(1)\right\} }$ when ${ n=1 }$, ${ T(n)=\Theta(1)\cdot n^3\leq Cn^3 }$ when ${ n \leq k-1 }$, assume for ${ T(n)\leq Cn^3 }$ consider ${ n = k }$, that is $$ T(k) = 4T(k/2)+k \leq C\cdot 4 \cdot \left(\frac{k}{2}\right)^3 + k =C\cdot \frac{k^3}{2}+k = Ck^3 - \left(C\cdot \frac{k^3}{2}-k\right) $$ Because ${ C\geq \frac{1}{2} }$, it's trivial to get ${ C\cdot \frac{k^3}{2}-k \geq 0 }$ Therefore, we can get the conclusion, for all ${n\in \mathbb{N}^+ , T(n)\leq Cn^3}$. That is ${ T(n) = O (n^3) }$

We just prove a strong conclusion, that is, for all ${ n\in \mathbb{N}^+ }$, we can get ${ T(n)\leq Cn^3 }$. Actually, we just need to prove that when ${ n\geq n_0 }$, we can find constant ${ C }$ to satisfy ${ T(n)\leq Cn^3 }$. Actually, we can prove there exists ${ n_0 >0 }$, such that ${ T(n)\leq 2n^3}$ when ${n>n_0 }$, that is ${ C=2 }$ (in fact ${ C>2 }$ is also OK). This is another strong conclusion, but for ${ C }$.

Let ${ n_0 = \max\{1,\Theta(1)\} }$. First, we prove ${ n=n_0 }$ is right $$ \begin{equation} \begin{aligned} T(n_0) &= 4(T(n_0/2))+n_0 \\ &= 4\left(4\left(T(n_0/4)\right)+n_0/2\right)+n_0 \\ &= \cdots \\ &= 4^{\lg_2 n_0} \cdot \Theta(1) + n_0 \cdot (1+2+\cdots+2^{\lg_2 n_0})\\ &={n_0}^2\cdot \Theta(1) + n_0 \cdot \frac{1-2^{\lg_2 n_0}}{1-2} \\ &= {n_0}^2\cdot \Theta(1) + (n_0 - 1)n_0 \end{aligned} \end{equation} $$ Because, ${ n_0 = \max\{1,\Theta(1)\} }$ that is ${ n_0 \geq \Theta(1) }$. Therefore, we can get $$ \begin{equation} \begin{aligned} T(n_0) &= {n_0}^2\cdot \Theta(1) + (n_0 - 1)n_0 \\ &\leq n_0^3 +n_0^2 -n_0 \end{aligned} \end{equation} $$ In the meantime, ${ n_0 \geq 1 }$, so ${ n_0^2-n_0 \leq n_0^3 }$. Then we can get $$ \begin{equation} \begin{aligned} T(n_0) &\leq n_0^3 +n_0^2 -n_0 \\ &\leq 2n_0^3 \end{aligned} \end{equation} $$ So, ${ n=n_0 }$ is corrected. Assume all the cases of ${ n <k, k>n_0 }$ satisfy ${ T(n)\leq 2n^3 }$, let's check ${ n=k }$: $$ T(k) = 4T(k/2)+k \leq 4 \left(\frac{k}{2}\right)^3 + k \leq \frac{1}{2}\cdot k^3 +k \leq 2k^3 $$

To sum up, in fact the prove from video is not very rigor, becasue the const ${ C }$ is not the same one in the cases of ${ n>1 }$ and ${n=1 }$. For the following proof I gived, the clue of my proof is fixing ${ C }$ or ${ n_0 }$ to prove ${ T(n) = O(n^3) }$.

In the following, we will prove that ${ T(n) = O(n^2) }$,

1. Guess: ${ T(n) = O(n^2) }$

2. Induction: Assume ${ k<n }$ is correct, that is

$$ T(k) \leq c_1 \cdot k^2 -c_2 \cdot k \quad \text{ for } k < n $$

Why we choose the assumption ${ T(k) \leq c_1 \cdot k^2 -c_2 \cdot k }$?

Out of intuition, maybe we will figure out ${ T(k) \leq c \cdot k^2 }$ at first, but we will find that ${T(n) \leq cn^2 + n}$, so we can not go on our induction. Therefore, this form may give us some inspiration, to use a stronger assumption to do induction.

1. Now, let’s check

$$ \begin{equation} \begin{aligned} T(n) &= 4T(n/2)+n \\ &\leq 4\left(c_1 (n/2)^2-c_2 (n/2)\right) + n \\ &= c_1 n^2 -2c_2\cdot n +n \\ &= c_1 n^2 -c_2 n - (c_2-1) \cdot n \end{aligned} \end{equation} $$

So, here we can let ${ c_2 > 1 }$ to guarantee ${ (c_2 -1)\cdot n > 0 }$. So we can finish our induction. Besides, for the base case

$$ \Theta(1) \leq c_1 -c_2 $$

Therefore, we need ${ c_2 >1 }$ and ${ c_1 > \Theta(1) + c_2 }$.

Recursion-tree method

Recursion-tree usually works and can give us an intuition to know the answer, but it’s slightly non-rigorous!

Technically, we should use resursion-tree method to find the answer and use substitution method to prove it rigorously.

Ex. ${ T(n)=T(n/4)+T(n/2)+n^2 }$

We can build a “Recursion Tree” as follow

First, we can know that the number of leaves is less than ${ n }$.

If we divide ${ T(n) }$ to four ${ T(n/4) }$ or two ${ T(n/2) }$, the number of leaves will be ${ n }$. But, here ${ n/4 + n/2 = 3n/4 <n }$, so the number of leaves must less than ${ n }$.

Then, we will calculate the sum of tree level by level. Through observation, we find that the sums of each level construct a geometric series (see the following figure).

Therefore, we can calculate the upper bound of ${ T(n) }$ (the height of tree is a finite number, but we treat it as a infinite geometric series.)

$$ \begin{equation} \begin{aligned} T(n) &< n^2 \cdot \sum_{i=0}^{\infty} \left(\frac{5}{16}\right)^i + \Theta(1) \cdot n \\ &= n^2 \cdot \lim_{i\rightarrow \infty} \frac{1-\left(\frac{5}{16}\right)^i}{1-\frac{5}{16}}+\Theta(1) \cdot n\\ &= \frac{16}{11} \cdot n^2 + \Theta(1) \cdot n \\ &= O(n^2) \end{aligned} \end{equation} $$

In the meantime, it’s easy to get ${ T(n)>n^2 }$, so ${ T(n) = o(n^2) }$. Therefore ${ T(n) = \Theta(n^2) }$.

Master method

We can treat the Master method as an application of the recursion-tree method. In detail, we apply resursion-tree method to a particular family (as below) of recurrences to get Master theorem.

$$ T(n) = aT(n/b) + f(n) \quad \text{ where } a \geq 1, b>1, \text{ and } f(n) \text{ is asymptotically positive} $$

Note! Asymptotically positive: there exists some ${ n_0 }$, when ${ n>n_0, f(n) >0 }$.

Compare ${ f(n) }$ with ${ n^{\log_b a} }$

Case #1: ${ f(n) = O\left(n^{\log_b a - \varepsilon}\right) }$ for some ${ \varepsilon >0 }$.

${\Rightarrow}$ ${ T(n) = \Theta\left(n^{\log_b a}\right) }$

Case #2: ${ f(n) = \Theta\left(n^{\log_b a}(\lg n)^k\right) }$ for some ${ k\geq 0 }$

${\Rightarrow}$ ${ T(n) = \Theta\left(n^{\log_b a}(\lg n)^{k+1}\right) }$

Case #3: ${ f(n)=\Omega(n^{\log_b a+\varepsilon}) }$, for some ${ \varepsilon >0 }$. And ${ af(n/b)\leq (1-\varepsilon’)\cdot f(n) }$ for some ${ \varepsilon’ >0 }$

${\Rightarrow}$ ${ T(n) = \Theta\left(f(n)\right) }$

Ex. ${ T(n)=4T(n/2)+n }$

Ans: Here ${ a=4,b=2,f(n)=n }$, compare ${ n^{\log_2 4} = n^2 }$ with ${ f(n)=n }$. ${ f(n)=O(n^{2-\varepsilon}) }$ here we can take ${ \varepsilon=1 }$. So, we are in Case #1, that means ${ T(n)=\Theta(n^{\log_2 4})= \Theta(n^2) }$

Ex. ${ T(n)=4T(n/2)+n^2 }$

Ans: Here we are in Case #2, because we can choose ${ k=0 }$, so ${ f(n)=n=\Theta\left(n^2(\lg n)^0\right) }$. Therefore, ${ T(n)=\Theta(n^2 \lg n) }$

Ex. ${ T(n)=4T(n/2)+n^3 }$

Ans: First, let’s check

$$ 4f(n/2) = 4(n/2)^3 = \frac{n^3}{2} \leq \frac{1}{2} f(n) $$

Here we take ${ \varepsilon’=\frac{1}{2} }$. And ${ f(n)=n^3 = \Omega(n^{2+\varepsilon}) }$, here we can let ${ \varepsilon = 1 }$. So we are in Case #3, then we can get ${ T(n)=\Theta(f(n))=\Theta(n^3) }$

Ex. ${ T(n)=4T(n/2)+n^2/\lg n }$. Warning: here Master method doesn’t apply to it.

Proof of Master Theorem

At first, we can draw the recursion tree of recurrence ${ T(n)=aT(n/b)+f(n) }$. Then, we can calculate the height of the tree. In ${ i^{th} }$ level, the cost of each note is ${ f(n/b^i) }$, and the cost of each leaf is ${ T(1)=\Theta(1) }$, so the height of tree ${ h }$ is ${ \log_b n }$. (Because ${ n / b^h = 1}$). Besides, in each level, each notes will have ${ a }$ children, so the number of leaves is ${ a^{\log_b n} = a^{\frac{\log_a n}{\log_a b}}=\left(a^{\log_a n}\right)^{\frac{1}{\log_a b}} = n^{\frac{1}{\frac{\log_b b}{\log_b a}}}=n^{\log_b a}}$

The recursion tree generated by ${ T(n)=aT(n/b)+f(n) }$¹.

Therefore, the total cost is

$$ T(n) = \Theta(n^{\log_b a}) + \sum_{i=0}^{\log_b n -1} a^i f(n/b^i) $$

Let ${ g(n)=\sum_{i=0}^{\log_b n -1} a^i f(n/b^i) }$.

Case #1: Because ${ f(n)=O(n^{\log_b a - \varepsilon}) }$, so there exists ${ c>0,n_0 }$ such that ${ f(n)\leq c\cdot n^{\log_b a - \varepsilon} }$, when ${ n>n_0 }$. Therefore, when ${ n>n_0 }$, we can get

$$ \begin{equation} \begin{aligned} g(n) &\leq \sum_{i=0}^{\log_b n -1} a^i c\cdot (n/b^i)^{\log_b a - \varepsilon}\\ &= c\cdot n^{\log_b a - \varepsilon} \cdot \sum_{i=0}^{\log_b n -1} a^i (1/b^i)^{\log_b a - \varepsilon} \\ &= c\cdot n^{\log_b a - \varepsilon} \cdot \sum_{i=0}^{\log_b n -1} \left(\frac{ab^\varepsilon}{b^{log_b a}}\right)^i \\ &= c\cdot n^{\log_b a - \varepsilon} \cdot \sum_{i=0}^{\log_b n -1} \left(b^\varepsilon\right)^i \end{aligned} \end{equation} $$

Then we get a geometric series, so

$$ \begin{equation} \begin{aligned} g(n) &\leq c\cdot n^{\log_b a - \varepsilon} \cdot \sum_{i=0}^{\log_b n -1} \left(b^\varepsilon\right)^i \\ &= c\cdot n^{\log_b a - \varepsilon} \cdot \frac{1-(b^{\varepsilon})^{log_b n}}{1-b^{\varepsilon}} \\ &= c\cdot n^{\log_b a - \varepsilon} \cdot \frac{n^{\varepsilon}-1}{b^{\varepsilon}-1} \\ &\leq \frac{c\cdot n^{\log_b a - \varepsilon} \cdot n^{\varepsilon}}{b^{\varepsilon}-1} \\ &= \frac{c}{b^{\varepsilon}-1} \cdot n^{\log_b a} \end{aligned} \end{equation} $$

Because ${ b>1,\varepsilon>0 }$, we can get ${ \frac{c}{b^{\varepsilon}-1}>0 }$. Therefore, ${ g(n)=O(n^{\log_b a}) }$, that means

$$ T(n)=\Theta(n^{\log_b a}) + O(n^{\log_b a}) = \Theta(n^{\log_b a}) $$

Case #2: Because ${ f(n)=\Theta(n^{\log_b a} (\lg n)^k), k\geq 0 }$, so ${ g(n)=\Theta\left(\sum_{i=0}^{\log_b n -1} a^i \left( \frac{n}{b^i}\right)^{\log_b a} \left( \lg \frac{n}{b^i}\right)^k \right) }$. Let ${ A= \sum_{i=0}^{\log_b n -1} a^i \left( \frac{n}{b^i}\right)^{\log_b a} \left( \lg \frac{n}{b^i}\right)^k}$, we have

$$ \begin{equation} \begin{aligned} A &= \sum_{i=0}^{\log_b n -1} a^i \left( \frac{n}{b^i}\right)^{\log_b a} \left( \lg \frac{n}{b^i}\right)^k \\ &= n^{\log_b a} \sum_{i=0}^{\log_b n -1} \left( \frac{a}{b^{\log_b a}} \right)^{i} \left( \lg \frac{n}{b^i}\right)^k \\ &= n^{\log_b a} \sum_{i=0}^{\log_b n -1} \left( \lg \frac{n}{b^i}\right)^k \end{aligned} \end{equation} $$

Let ${ B = \sum_{i=0}^{\log_b n -1} \left( \lg \frac{n}{b^i}\right)^k}$, we can get

$$ \begin{equation} \begin{aligned} B &= \sum_{i=0}^{\log_b n -1} \left( \lg \frac{n}{b^i}\right)^k \\ &= \sum_{i=0}^{\log_b n -1} \left( \lg n - \lg b^i \right)^k \\ &= \sum_{i=0}^{\log_b n -1} \left( (\lg n)^k + o\left((\lg n)^k\right) \right) \\ & = \log_b n \cdot \left( (\lg n)^k + o\left((\lg n)^k\right) \right) \\ &= \Theta \left( \log_b n \cdot (\lg n)^k \right) \\ &= \Theta \left( \frac{1}{\lg b} \lg n \cdot (\lg n)^k \right)\\ &= \Theta \left( (\lg n)^{k+1} \right) \end{aligned} \end{equation} $$

Therefore, ${ g(n)=\Theta(A)=\Theta(n^{\log_b a} B) = \Theta \left( n^{\log_b a}(\lg n)^{k+1} \right) }$.

Another proof with definition of ${ \Theta }$ is here

Because ${ f(n)=\Theta(n^{\log_b a} (\lg n)^k), k\geq 0 }$, so there exists ${ c_1>0,c_2>0,n_0>0 }$ such that ${ c_1\cdot n^{\log_b a} (\lg n)^k \leq f(n) \leq c_2\cdot n^{\log_b a} (\lg n)^k }$, when ${ n>n_0 }$. Therefore, we can get $$ \begin{equation} \begin{aligned} \sum_{i=0}^{\log_b n -1} a^i c_1\cdot (n/b^i)^{\log_b a} (\lg n/b^i)^k &\leq g(n) \leq \sum_{i=0}^{\log_b n -1} a^i c_2\cdot (n/b^i)^{\log_b a} (\lg n/b^i)^k \\ c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} a^i (1/b^i)^{\log_b a} (\lg n/b^i)^k &\leq g(n) \leq c_2\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} a^i (1/b^i)^{\log_b a} (\lg n/b^i)^k \\ c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k &\leq g(n) \leq c_2\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k \\ \end{aligned} \end{equation} $$ For the right part, replacing ${ b^i }$ as ${ b^0 = 1}$ we can get $$ \begin{equation} \begin{aligned} c_2\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k & \leq c_2\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n)^k\\ & = c_2\cdot n^{\log_b a} \cdot \log_b n \cdot (\lg n)^k \\ &= c_2\cdot n^{\log_b a} \cdot \frac{\lg n}{\lg b} \cdot (\lg n)^k \\ & = \frac{c_2}{\lg b} \cdot n^{\log_b a} \cdot (\lg n)^{k+1} \end{aligned} \end{equation} $$ For the left part, we can get $$ \begin{equation} \begin{aligned} c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k &\geq c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^{\log_b n -1})^k \\ & = c_1\cdot n^{\log_b a} \cdot (\lg n)^k \sum_{i=0}^{\log_b n -1} \left(\frac{\lg n -\lg b^i}{\lg n}\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot (\lg n)^k \sum_{i=0}^{\log_b n -1} \left(1 - i\cdot \frac{\lg b}{\lg n}\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot (\lg n)^k \sum_{i=0}^{\log_b n -1} \left(\log_b n \cdot \frac{\lg b}{\lg n}- i\cdot \frac{\lg b}{\lg n}\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot (\lg n)^k \cdot \left(\frac{\lg b}{\lg n}\right)^k \cdot \sum_{i=0}^{\log_b n -1} \left(\log_b n - i\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot \sum_{i=0}^{\log_b n -1} \left(\log_b n - i\right)^k \end{aligned} \end{equation} $$ Notice that the sqeuence of summation is ${ (\log_b n)^k, (\log_b n -1)^k, \cdots, 1^k }$, we can change the order as $$ \begin{equation} \begin{aligned} c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k &\geq c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot \sum_{i=0}^{\log_b n -1} \left(\log_b n - i\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot \sum_{i=1}^{\log_b n} i^k \\ \end{aligned} \end{equation} $$ According to the "Inequality" that arithmetric average is bigger than geometric average, that is $$ \frac{1}{n} \cdot \sum_{i=1}^n x_i \geq \sqrt[n] {\prod_{i=1}^n x_i} $$ Therefore, we can get $$ \begin{equation} \begin{aligned} c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k &\geq c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot \sum_{i=1}^{\log_b n} i^k \\ & \geq c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot {\log_b n} \cdot \sqrt[\log_b n] {\prod_{i=1}^{\log_b n} (i)^k} \\ &= c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot {\log_b n} \cdot \left(\sqrt[\log_b n] {(\log_b n)!}\right)^k \end{aligned} \end{equation} $$ According to [Stirling's approximation](https://en.wikipedia.org/wiki/Stirling's_approximation), we have $$ n! \geq \sqrt {2\pi n} \left(\frac{n}{e}\right)^n e^{\frac{1}{12n+1}} $$ So, we can get (let ${ m=\log_b n }$) $$ \begin{equation} \begin{aligned} c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k &\geq c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot {\log_b n} \cdot \left(\sqrt[m] {m!}\right)^k \\ &\geq c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot {\log_b n} \cdot \left(\sqrt[m] {\sqrt {2\pi m} \left(\frac{m}{e}\right)^{m} e^{\frac{1}{12m+1}}}\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot (\log_b n)^{k+1} \cdot \left(\frac{1}{e}\right)^k \cdot \left(\sqrt[m] {\sqrt {2\pi m} \cdot e^{\frac{1}{12m+1}}}\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot (\log_b n)^{k+1} \cdot \left(\frac{1}{e}\right)^k \cdot \left( {2\pi}^{\frac{1}{2 m}} \cdot (m)^{\frac{1}{2 m}} \cdot e^{\frac{1}{12m^2+m}} \right)^k \end{aligned} \end{equation} $$ Here, it's trivial to check the below funtions are monotone decreasing (because ${n>1 \Rightarrow m=\log_b n >0 }$), and their limits are ${ 1 }$, which is also their lower bound. $$ {2\pi}^{\frac{1}{2 m}} \geq 1 , (m)^{\frac{1}{2 m}} \geq 1, e^{\frac{1}{12m^2+m}} \geq 1 $$ So, we finally get the left part $$ \begin{equation} \begin{aligned} g(n) &\geq c_1\cdot n^{\log_b a} \cdot \sum_{i=0}^{\log_b n -1} (\lg n/b^i)^k \\ &\geq c_1\cdot n^{\log_b a} \cdot \left(\lg b\right)^k \cdot (\log_b n)^{k+1} \cdot \left(\frac{1}{e}\right)^k \\ &= c_1\cdot n^{\log_b a} \cdot (\lg n)^{k+1} \cdot \left(\frac{1}{e}\right)^k \end{aligned} \end{equation} $$ Combining the left and right part, in the end, we prove ${ g(n) = \Theta(n^{\log_b a} \cdot (\lg n)^{k+1}) }$. Q.E.D

Case #3: Because ${ f(n) }$ is one of the items in ${ g(n) }$, so ${ g(n)=\Omega(f(n)) }$. If we want to prove ${ g(n)=\Theta(f(n)) }$, we just need to prove ${ g(n)=O(f(n)) }$.

In this case, we have ${ af(n/b) \leq (1-\varepsilon’)f(n) }$, that is ${ f(n/b) \leq ((1-\varepsilon’)/a)f(n) }$, so we can get ${ f(n/b^i) \leq ((1-\varepsilon’)/a)^i f(n) }$, that is, ${ a^i f(n/b^i) \leq (1-\varepsilon’)^i f(n) }$. (When ${ n/b^i }$ is sufficient large enough).

Therefore, we can get

$$ \begin{equation} \begin{aligned} g(n) &= \sum_{i=0}^{\log_b n -1} a^i f(n/b^i)\\ &\leq \sum_{i=0}^{\log_b n -1} (1-\varepsilon')^i f(n) \\ &= f(n) \cdot \sum_{i=0}^{\log_b n -1} (1-\varepsilon')^i \\ &\leq f(n) \cdot \sum_{i=0}^{\infty} (1-\varepsilon')^i \end{aligned} \end{equation} $$

Note ${ 1-\varepsilon’ <1}$, so

$$ \begin{equation} \begin{aligned} g(n) &\leq f(n) \cdot \sum_{i=0}^{\infty} (1-\varepsilon')^i \\ &= f(n) \cdot \frac{1}{\varepsilon'} \end{aligned} \end{equation} $$

So, ${ g(n)=O(f(n)) \Rightarrow g(n)=\Theta(f(n)) }$. And, ${ f(n)=\Omega(n^{\log_b a+\varepsilon}) }$, for some ${ \varepsilon >0 }$. Then we can get

$$ T(n)=\Theta(n^{\log_na b} ) +\Theta(f(n))=\Theta(f(n)) $$