$$x\in\mathrm N ^\circ (x_\ominus, \delta)\to a\times g(x)<f(x)<b\times g(x)$$

$$\begin{aligned} f(x)\sim g(x)&\iff g(x)\sim f(x)&\iff &a\in\mathrm N(1_{S},\zeta)\land b\in \mathrm N(1_{S},\zeta)\\ f(x)\in o(g(x))&\iff g(x)\in\omega(f(x))&\iff &a\in\mathrm N(0_S, \zeta)\land b\in\mathrm N(0_S, \zeta)\\ f(x)\in O(g(x))&\iff g(x)\in\Omega(f(x))&\iff &a\in\mathrm S\land b\in S\\ f(x)\in\Theta(g(x))&\iff g(x)\in\Theta(f(x))&\iff &f(x)\in O(g(x))\land f(x)\in \Omega(g(x)) \end{aligned}$$

$$f(n) = af\left(\frac n b\right) + g(n),\quad n > b,a\ge1,b>1$$

$$f(n) \in \begin{cases} \Theta(n^{\log_b a}),&g(n)\in O(n^{\log_b a - \zeta})\\ \Theta(g(n)),&g(n)\in\Omega(n^{\log_b a+\zeta})\\ \Theta(n^{\log_ba}\log n),&g(n)\in\Theta(n^{\log_ba}) \end{cases}$$

$$\begin{aligned} f(n) &= af\left(\frac n b\right) + g(n)\\ &=a\left(af\left( \frac{n}{b^2}\right) + g\left(\frac n b\right)\right) + g(n)\\ &=\cdots\\ &=a^{m + 1}f\left(\frac{n}{b^{m + 1}} \right) + \sum_{k = 1}^m a^kg\left(\frac{n}{b^k} \right) \end{aligned}$$

$$\begin{aligned} f(n) &= af\left(\frac n b\right) + g(n)\\ &=a^{m + 1}f\left(\frac{n}{b^{m + 1}} \right) + \sum_{k = 1}^m a^kg\left(\frac{n}{b^k} \right)\\ &=a^{\log_bn}f\left(\frac{n}{b^{\log_b n}}\right)+ \sum_{j = \lfloor\log_b n\rfloor - k,k=1}^{\lfloor\log_b n\rfloor}a^{\lfloor\log_b n\rfloor - j}g\left(b^j \right)\\ &=a^{\log_bn}f\left(\frac{n}{b^{\log_b n}}\right)+ a^{\log_bn}\sum_{k=1}^{\lfloor\log_b n\rfloor}h\left(b^k \right)\\ &\in \Theta\left(a^{\log_bn}f\left(\frac{n}{b^{\log_b n}}\right)\right) + \Theta\left(n^{\log_ba}\sum_{k = 1}^{\lfloor\log_b n\rfloor}h\left(b^k\right)\right)\\ &\in \Theta\left(n^{\log_b a} \right) + \Theta\left(n^{\log_ba}\sum_{k = 1}^{\lfloor\log_b n\rfloor}h\left(b^k\right)\right)\\ \end{aligned}$$

$$h(n) =\frac{g(n)}{n^{\log_ba}}$$