一个递归计算与时间复杂度分析的例子

使用 Python 实现 $x^n$ 的递归计算：

def f(x, n): if n == 0: return 1 else: return x * f(x, n-1)

我们定义用来计算时间复杂度的函数为 $T$, 则上面的 $x^n$ 的递归计算可以使用如下递推关系来表示：

$$ T(n) = T(n-1) + 1 $$

这样，有 $T(n) = T(n-i) + i$, 故而

$$ \begin{aligned} T(n) &= T(n-(n-1)) + n-1\\ &=T(1) + n-1\\ &=\Theta (1) + n-1\\ &=\Theta(n) \end{aligned} $$

其中，$f \in \Theta(g)$ 表示：存在自然数 $n_0$ 和正数 $cc_1,c_2$, 对于所有的 $n\geq n_0$ 都成立

$$ c_1g(n) \leq f(n) \leq c_2g(n). $$

综上所述，$x^n$ 在上面的递归定义下的时间复杂度为 $\Theta(n)$.