递归法求解

首先对若干符号及其相关概念进行说明。

---

Θ：渐近紧确界

定义：Θ(g(n)) 表示由所有满足条件的函数 f(n) 构成的集合，即存在正数 c1、c2 以及 n0，使得对于所有 n ≥ n0，均有 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)。

换句话说，当 n 超过某个特定值后，f(n) 将处于 c1g(n) 与 c2g(n) 所构成的区间之内。

例如，在证明函数 2n² - 3n 的渐近紧确界为 Θ(n²) 时，我们有不等式：c₁n² ≤ 2n² - 3n ≤ c₂n²。在求解该不等式时，应先确定 n₀ 的值，再寻找合适的常数 c。

具体而言，c₁ ≤ 2 - 3/n。若设定 n₀ = 5，则可得 c₁ ≤ 7/5。这表明存在一个不大于 7/5 的常数 c₁，在满足 n ≥ n₀ 的条件下，上述不等式成立。因此可以得出结论：n² 是该函数的渐近紧确界。

---

O：渐近上界

定义：O(g(n)) 表示由所有满足条件的函数 f(n) 构成的集合，即存在正数 c 和 n₀，使得对于所有 n ≥ n₀，均有 0 ≤ f(n) ≤ cg(n)。

该定义表明，在某个临界点之后的所有输入规模中，f(n) 的增长速度不会超过 cg(n)，这一记号通常用于描述算法运行时间的最坏情况。

---

Ω：渐近下界

定义：Ω(g(