主定理狗都不学

略标题党。借用了前一个的标题。

验证仍然是带有一点不靠谱的，实际上可以采用更加靠谱和直接的办法：

暴力递归。

以下是使用暴力递归法来解前一个的三个例子：

例 1

众所周知，把 $n$ 开根到 $1$ 为止的次数是 $\log_2\log_2 n$。

例 2

$\log(n/2^k)$ 全部放成 $\log n$，然后等比数列求和。

例 3

不妨设 $n=2^{k}$，记 $T(2^k)=f_k$，那么 $f_k=3f_{k-1}+4f_{k-2}+2^k$。

记 $g_k=f_k+2^{k+1}/3$，那么 $g_k=3g_{k-1}+4g_{k-2}$。

容易看出 $g_k=a4^k+b(-1)^k$（高中数学竞赛基础内容，瞪眼也能看出来）

所以 $T(2^k)=a4^k+b(-1)^k-2^{k+1}/3=O(4^k)$，所以 $T(n)=O(n^2)$。

虽然其实是非常正常和直接的思路，但是好像很多人不会这种东西。

计算量不会很大的。