#2.3
##(a)
由题解，假定对于某个常数c,有$O(n)≤cn$
且$T(n)=3T(n/2)+O(n)$
那么有
\begin{eqnarray}
T(n) & ≤ & 3T(n/2)+cn \
& ≤ & 3[3T(n/4)+cn/2]+cn = 9T(n/4)+3cn/2+cn \
& ≤ & 9[3T(n/8)+cn/4]+3cn/2+cn=27T(n/8)+9cn/4+3cn/2+cn \
& \ldots &
\end{eqnarray}
从而，通项公式为：
$$T(n)≤3^kT(n/2^k)+\sum_{i=0}^{k-1} (3/2)^icn$$
很明显，$k=log_2n$
##(b)
由题解，假定对于某个常数c,有$O(1)≤c$
且$T(n)=T(n-1)+O(1)$
那么有
\begin{eqnarray}
T(n) & ≤ & T(n-1)+c \
& ≤ & T(n-2)+2c \
& ≤ & T(n-3)+3c \
& \ldots &
\end{eqnarray}
从而，通项公式为：
$$T(n)≤T(n-k)+kc$$
很明显，$k=n$
所以，$$T(n)=O(n)$$
#2.4
首先，介绍求解递归式的几个方法：
1 主方法
2 替代法1
2
3猜测解的形式。
通过推导验证。
解出常数。
3 递归树方法
4 递推法
##算法A:
$T(n)=5T(n/2)+O(n)$
很明显，递归式满足主定理模式，a=5，b=2，$f(n)=n$
$log_ba=log_25$,
又$∵ log_25>1$,
$∴T(n)=O(n^{log_25})$
##算法B:
$T(n)=2T(n-1)+O(1)$
采用递推法，
\begin{eqnarray}
T(n) & ≤ & 2T(n-1)+c \
& ≤ & 2^2T(n-2)+2c \
& ≤ & 2^3T(n-3)+3c \
& \ldots &\
& ≤ & 2^nT(1)+nc \
\end{eqnarray}
所以，$T(n)=O(2^n)$
##算法C:
$T(n)=9T(n/3)+O(n^3)$
很明显，递归式满足主定理模式，a=9，b=3，$f(n)=n^3$
$log_ba=log_39=2$,
又$∵ n^2<n^3$,
$T(n)=O(n^3)$
当n足够大时，很明显$T_a(n)<T_c(n)<T_b(n)$
所以算法A最优。
#2.5
a)用递推法很快可以求出
$$T(n) = O(n^{log_32})$$
b)用主方法
$$T(n) = O(n^{log_45})$$
c)用主方法
$$T(n) = O(nlogn)$$
d)用主方法
$$T(n) = O(n^2logn)$$
e)用主方法
$$T(n) = O(n^3logn)$$
f)用替代法，由于前面是$log_{25},所以我们猜测大影响在后面 $$$T(n) = O(n^{3/2} log n)$$
g)用递推法 $$T(n) = O(n)$$
h) 用递推法$$T(n) = O(n^c+1)$$
i) 用递推法$$T(n) = O(c^n)$$
j)用递推法
$$T(n) = O(2^n)$$
k)