则（3）式转换为：
C1*max(g1,g2) <= t1(n)+t2(n) <=c2*2max(g1,g2) 所以当c1＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)时，当n>=n0时上述不等式成立。 证毕。
习题2.2
2. 请用错误！未找到引用源。的非正式定义来判断下列断言是真还是假。 a. n(n + 1)/2 ∈ O(n3) b. n(n + 1)/2 ∈ O(n2) c. n(n + 1)/2 ∈ Θ(n3) d. n(n + 1)/2 ∈ Ω(n) 答：c假，其它真。
5.按照下列函数的增长次数对它们进行排列（按照从低到高的顺序）
(n?2)!, 5lg(n+100)10
, 22n
, 0.001n4
+3n3
+1, ln2
n,错误！未找到引用源。3n
.
答：习题2.3
1. 计算下列求和表达式的值。
答
，
：
3. 考虑下面的算法。
a． 该算法求的是什么？ b． 它的基本操作是什么？ c． 该基本操作执行了多少次？
d． 该算法的效率类型是什么？
e． 对该算法进行改进，或者设计一个更好的算法，然后指出它们的效率类型。
如果做不到这一点，请试着证明这是不可能做到的。
9.证明下面的公式：
可以使用数学归纳法，也可以像10岁的高斯一样，用洞察力来解决该问题。这个小学生长大以后成为有史以来最伟大的数学家之一。 数学归纳法：
高斯的方法：
习题2.4
1. 解下列递推关系 （做a,b） a.
?x(n)?x(n?1)?5当n>1时 ??x(1)?0 解：
b.
解：
?x(n)?3x(n?1)??x(1)?4当n>1时
2. 对于计算n!的递归算法F(n)，建立其递归调用次数的递推关系并求解。