请求协助证明递推式T(n)=Ω(n²)以完成T(n)=Θ(n²)推导

数学归纳法（最直接的方式） #

$\Omega(n^2)$的核心定义是：存在常数$c>0$和$n_0$，当$n\geq n_0$时，$T(n)\geq c\cdot n^2$。按以下步骤操作：

1. 基例验证：选取足够大的$n_0$（比如$n=1$或$n=2$，根据你的递归式调整），找到一个合适的小正数$c$（比如$1/4$、$1/2$），使得$T(n_0)\geq c\cdot n_0^2$成立。
2. 归纳假设：假设对于所有$k < n$，$T(k)\geq c\cdot k^2$均成立。
3. 归纳推导：将递归式代入假设，推导$T(n)\geq c\cdot n^2$。举个例子，若递归式为$T(n) = 2T(n/2) + n^2$，代入后得：
   $$T(n)\geq 2\cdot c\cdot (n/2)^2 + n^2 = \frac{c}{2}n^2 + n^2$$
   只要取$c\leq2$（比如$c=1$），就能满足$\frac{c}{2}n^2 + n^2 \geq c\cdot n^2$，从而完成归纳。

主定理（针对标准递归式） #

如果你的递归式符合形式$T(n) = aT(n/b) + f(n)$（$a\geq1$，$b>1$），直接用主定理判断：

• 若$\log_b a = 2$（比如$a=4$，$b=2$），且$f(n)=\Theta(n^{2)$，则$T(n)=\Theta(n}2)$，自然包含$\Omega(n^2)$。
• 若$f(n)=\Omega(n^{2+\epsilon})$（$\epsilon>0$）且满足正则条件（$a\cdot f(n/b)\leq k\cdot f(n)$，$k<1$），则$T(n)=\Theta(f(n))$，此时$f(n)$的下界就是$T(n)$的下界。

递归树法 #

将递归式展开为递归树，逐层计算代价并求和：

• 分析每一层的代价下界，累加所有层的代价后，可得到$T(n)$的总代价至少为$c\cdot n^{2$，直接证明$\Omega(n}2)$。

内容的提问来源于stack exchange，提问作者Xin Cheng