华中科技大学：计算机算法基础（王多强）：习题2003

∵g(n)=O(1)
∴ 可令 g(n)=c1(或简单令 g(n)=1)
同理，
∵ f(n)=O(n)
∴ 可令 f(n)=c2n(或简单令 f(n)=n),
可设 c1=c2=c
化简
T(n)=2T(n/2)+f(n)
=2T(n/2)+cn
=4T(n/4)+2(cn/2)+cn=4T(n/4)+2cn
=…
=2kT(n/2k)+kcn
若 n=2k,则 k=logn
∴T(n)=cn+cnlogn=O(nlogn)
当 n∈[2 k,2k+1),T(n)=cn+cnlogn=Θ(nlogn)
∵g(n)=O(1)
∴ 可令 g(n)=c1(或简单令 g(n)=1)
同理，
∵ f(n)=O(1)
∴ 可令 f(n)=c2(或简单令 f(n)=1),
可设 c1=c2=c
化简
T(n)=2T(n/2)+f(n)
=2T(n/2)+c
=4T(n/4)+2c+c
=8T(n/8)+22c+2c+c=…
=2kT(n/2k)+(1+2+22+…+2 k-1)c=cn+(2k-1)c
=2cn-c=O(n)