正确性

在我们对程序进行时间复杂度的估计之后，我们需要一些方法检验我们所估计的结果是否正确。
有一些概念：

• 算法中语句执行次数：T（n）

因为算法所花费的时间和算法中语句的执行次数成正比，所以可以将T（n）理解为实际的运行时间。

• 时间复杂度O(n)，也可以写成O（f（n））
• 辅助函数 f（n），一般有 n/n^2/n^3/logn/nlogn/n^2logN 等等

三者之间的关系如下：
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的时间复杂度.
这样，我们巧妙的用极限的思想选取最高次项，来契合时间复杂度的本质（保留最高次项，忽略低阶项）。
参考：时间复杂度的通俗讲法
检验复杂度分析的正确性的方法本质
在上面的的概念中，我们可以用实际的运行时间来代表T（n），然后通过时间复杂度的极限表达式 T（n）/f（n） 的性质来入手，进而求出 f（n），而后得出时间复杂度。

1. 方法一

按照时间复杂度O（n）来分析，如果估计正确，则：
当 n 扩大两倍时，

• 线性的运行时间乘以2。
• 二次程序的运行时间乘以4。
• 三次程序的运行时间乘以8。
• 对数时间运行的程序，运行时间增加一个常数。
• 以O（NlogN）时间运行的程序，运行时间比以前的运行时间的两倍多一点。

注意：以上的倍数关系都是约数。
上述结论我们可以将 2*n 代入f（n）中很容易的得出。

原理

通过 n 进行 n*2 处理，观察T（n）的变化情况，从而选择切合的 f（n）。

缺点：

当f(n)中的低阶项的系数相对的大，而N又不是足够大（也就是说最高阶项的变化被大系数低阶项的变化所掩盖了），此时运行时间的变化量很难观察清楚，尤其分辨线性程序还是O（NlogN）程序是很困难的。这种方法虽然直观，但是是比较粗略的一种估计方法。

2. 方法二

原理

通过T（n）/f（n）的收敛性入手。
随着n的增大：

• 若f（n）估计正确，则 T（n）/f（n） 应该会收敛于一个常数。
• 若 f（n） 估计过小，则 T（n）/f（n） 则算出的值应该发散。
• 若 f（n） 估计过大，则T（n）/f（n） 应该收敛于0.

具体的例子见书P25 中表。

分析

可以分析出简单程序的复杂度，且分析过程可以通过编程实现。
需要注意的是，有些复杂度之间差别不是很大，比如 n^2和 n^2logn,因为对数增长的很慢，此时用这种方法有时候不能精确的分析出二者差别。

分析结果的准确性

也就是说，我们分析出的结果，是否能正确的表征程序的运行时间呢？
在有些情况下，平均运行时间显著小于最坏情况的运行时间，此时最坏情况可能是由于某个不良输入导致的，但是在实践中基本不会出现该情况。所以这种情况下，我们对于时间复杂度的估计是过大的。【当然，有些情况下，出现最坏次数的情况比较多，此时我们对时间复杂度的估计是还算合理的】
遗憾的是，对于大多数这种问题，平均情形的分析是极其复杂的（有些算法甚至是未解决的），最坏情况的分析尽管有些过分悲观，但是确实已知的最好的分析结果。